삼성 SW 역량테스트 백준 연구소 14502

2021-04-21

BOJ, 백준, 삼성SW역량테스트, 알고리즘

1. 문제 링크

삼성 SW 역량테스트 기출 백준 연구소 14502

2. 문제 조건

연구소는 크기가 N×M입니다.
연구소에서 빈곳 0, 벽 1, 바이러스 2의 값이 주어지게 됩니다.
벽을 3개만 세운 뒤 바이러스가 퍼질 수 없는 안전영역의 최댓값을 구하는 문제입니다.
지도의 세로 크기 N과 가로 크기 M (3 ≤ N, M ≤ 8)

3. 컴퓨팅 사고

0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다. 라는 조건이 있는 문제입니다.

이 문제를 풀때 가장 중요한점은 DFS로 접근해야 하는가? BFS로 접근해야 하는가를 많이 고민하였던 문제였습니다.

Basement 조건이 벽을 3개 세울 때 조합의 경우의 수를 사용하기 위해서 DFS를 사용하였으며, 연구소에서 바이러스들이 전염시키는 과정은 BFS로 풀이를 진행하였습니다.

값을 입력받고 빈칸과 바이러스의 좌표를 담고 있는 벡터에 해당 값들을 넣어주게 됩니다.
빈칸을 기준으로 DFS를 수행한다. 따라서,조합의 경우라고 생각하면 됩니다. N(빈칸의 개수중)에서 3개를 뽑는 경우의 수라고 생각을 합니다.
DFS 에서의 수행은 빈칸의 개수가 기준이 되므로 empty_size를 선언해서 받아오게 하였습니다.
CNT 값이 3일 경우 3개의 벽을 모두 세운 경우이므로 기존의 값은 변화가 되면 안되기때문에 맵을 Copy시켜줍니다.
이제 BFS를 수행하기위해 각각의 경우에 있어서 Check변수가 1일 경우에만 벽을 세워주게 됩니다.
바이러스가 전파시에 현재 바이러스의 값 2인 좌표 (x,y)의 점을 기준으로 BFS를 수행합니다.
모든 BFS경우를 돌고나서 아직 전염되지 않은 값이 있는곳이 안전지대입니다. 그 곳의 값을 safe_size 카운팅 시켜줍니다.
각 경우마다 안전영역의 최대의 값을 구해주어야하므로 최댓값을 갱신시켜줍니다.
각 경우마다 경우의 수가 달라지므로 visited 변수를 초기화 시켜줍니다.

즉, DFS 반복 → basement 확인 → BFS (x,y)좌표로 부터 바이러스 전염 → 안전영역의 최댓값

3.1. 다시 풀어보았습니다.

(1) N*M의 보드가 주어집니다. (3 ≤ N, M ≤ 8)의 범위를 갖습니다.

바이러스의 확산의 벽을 3개를 세워야합니다.
맵에서 벽을 3개를 세우는 경우를 어떻게 찾아낼까가 가장 핵심이 되는 문제였습니다. 저 같은 경우는 하나의 리스트에 x,y좌표를 담고있는 Graph클래스를 하나 선언하여 ‘0’ 즉, 빈칸의 좌표값을 모두 리스트에 담아주었습니다. 그리고나서 DFS 백트래킹을 통하여 N개(모든 빈칸의 리스트)중에서 M개(3개를 선택) 하는 경우의 순열의 값들을 모두 구해주게 하였습니다. 예를 들어, 안전영역리스트에 1,2,3,4,5 가 주어졌다고 가정하면 여기서 벽을 세우는 경우는 어떻게 될까요? (1,2,3), (1,2,4),(1,2,5),(2,3,4) …. 등 다양한 경우의수가 나올 수 있게됩니다. 이 경우를 모두 체크해나갈 수 있습니다. 그리고 주의해야할 경우는 벽을 3개 모두세웠을 경우 현재 맵의 정보들이 변화하면 안되기때문에 각 경우의수마다 새로 배열들을 copy하여 갱신시켜서 매 경우를 체크해나가야합니다.

(2) 0:빈칸, 1:벽, 2:바이러스 벽이 세워지고 바이러스가 상하좌우로 퍼져나가게 합니다.

(3) 최종적인 프로세스는 벽을 3개 세우는 모든 경우의 수를 찾아주고 각 경우마다 벽을 세우고나서 바이러스를 퍼트립니다. 그리고 안전영역에 있는 최댓값 갱신해나가면 정답을 노출해낼 수 있습니다. 전반적으로 한번 풀어봤던 경험이 있었던지라 30분정도 소요되었던 문제였습니다.

(4) 순열과 조합을 각각 돌려서 테스트해보았더니 큰 차이를 얻을 수 있었습니다.

약 공간복잡도 메모리차이가 2배이상차이가나고, 시간복잡도 차이에서는 1.5배이상 차이가 나게되었습니다. 확실히 순열로 돌리게 될 경우 상당히 많은 경우의 수가 나타난다는것을 알 수 있었습니다.

제출 번호 아이디 문제 결과 메모리 시간 언어 코드 길이
28575832 kgh940525 14502 맞았습니다!! 149348 636 Java 8 / 수정 5431
28575134 kgh940525 14502 맞았습니다!! 303684 1000 Java 8 / 수정 4086

4. 풀이 코드

JAVA 재풀이 코드

package Samsung.ing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 연구소_14502번 {
    static int n,m;
    static int answer;
    static int[][] map;
    static int[][] copyMap;
    static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};       // 북동남서
    static boolean[] isCheckSafe;
    static boolean[][] isCheckVirus;
    static List<Graph> safeAreaList;
    static List<Graph> safeAreaSelectList;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        answer = 0;
        safeAreaList = new ArrayList<>();
        safeAreaSelectList = new ArrayList<>();

        int idx = 0;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<m; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 0){
                    safeAreaList.add(new Graph(i,j));
                }
            }
        }
        isCheckSafe = new boolean[safeAreaList.size()];
        dfs_combination(0,0);                    //조합으로 풀기
        // dfs_permutation(0);                   //순열으로 돌리기
        System.out.println(answer);
    }

    private static void dfs_combination(int idx, int cnt) {
        // 벽을 세개 다 세운 경우
        if(cnt == 3){
            // map copy
            copyMap = new int[n][m];
            isCheckVirus = new boolean[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    copyMap[i][j] = map[i][j];
                }
            }
            // 복사된 맵에 벽 세우기
            for (int i = 0; i < safeAreaList.size(); i++) {
                if(isCheckSafe[i]){
                    int safeX = safeAreaList.get(i).x;
                    int safeY = safeAreaList.get(i).y;
                    copyMap[safeX][safeY] = 1;
                }

            }

            // 바이러스 전파
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(copyMap[i][j] == 2 && !isCheckVirus[i][j]) {
                        virusSpread(i,j);
                    }
                }
            }
            // 안전영역 구하기
            getSafeAreaSize();
            return;
        }
        for(int i=idx; i<safeAreaList.size(); i++){
            if(isCheckSafe[i]) continue;
            isCheckSafe[i] = true;
            dfs_combination(i,cnt+1);
            isCheckSafe[i] = false;
        }
    }

    private static void dfs_permutation(int cnt) {
        // 벽을 세개 다 세운 경우
        if(cnt == 3){
            // map copy
            copyMap = new int[n][m];
            isCheckVirus = new boolean[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    copyMap[i][j] = map[i][j];
                }
            }
            // 복사된 맵에 벽 세우기
            for (int i = 0; i < safeAreaSelectList.size(); i++) {
                Graph graph = safeAreaSelectList.get(i);
                int x = graph.x;
                int y = graph.y;
                copyMap[x][y] = 1;
            }

            // 바이러스 전파
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(copyMap[i][j] == 2 && !isCheckVirus[i][j]) {
                        virusSpread(i,j);
                    }
                }
            }
            // 안전영역 구하기
            getSafeAreaSize();
            return;
        }
        for(int i=0; i<safeAreaList.size(); i++){
            Graph graph = safeAreaList.get(i);
            if(isCheckSafe[i]) continue;
            isCheckSafe[i] = true;
            safeAreaSelectList.add(new Graph(graph.x, graph.y));
            dfs_permutation(cnt+1);
            safeAreaSelectList.remove(safeAreaSelectList.size()-1);
            isCheckSafe[i] = false;
        }
    }

    private static void getSafeAreaSize() {
        int areaSize = 0;
        for (int i = 0; i < n; i++) {
            for(int j=0; j< m; j++){
                if(copyMap[i][j] == 0) areaSize++;
            }
        }
        answer = Math.max(answer, areaSize);
    }

    private static void virusSpread(int x,int y) {
        Queue<Graph> q = new LinkedList<>();
        q.add(new Graph(x,y));
        isCheckVirus[x][y] = true;

        while(!q.isEmpty()){
            Graph graph = q.remove();
            int dx = graph.x;
            int dy = graph.y;

            for(int i=0; i<4; i++){
                int mx = dx + dir[i][0];
                int my = dy + dir[i][1];
                if(isCheckRange(mx, my)) continue;
                if(copyMap[mx][my] == 0 && !isCheckVirus[mx][my]){
                    copyMap[mx][my] = 2;
                    isCheckVirus[mx][my] = true;
                    q.add(new Graph(mx,my));
                }
            }

        }

    }

    private static boolean isCheckRange(int mx, int my) {
        if(mx < 0 || mx >= n || my < 0 || my >= m){
            return true;
        }
        return false;
    }

    private static class Graph {
        int x;
        int y;

        public Graph(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

C++

//
//  연구소14502.cpp
//  algorithm-ps
//
//  Created by kgh on 2020/09/07.
//  Copyright © 2020 kgh. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n,m = 0;
const int MAX = 8;
int map[MAX][MAX];
int copy_map[MAX][MAX];
vector<pair<int,int>> empty;
vector<pair<int,int>> virus;

int empty_size = 0;
int check[MAX*MAX];     // size를 MAX * MAX를 해준이유는 빈칸이 N*M까지 나올 수 있기 때문입니다.
int visited[MAX][MAX];
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int ans = -1;
void bfs(int x,int y){
    
    queue<pair<int,int>> q;
    q.push({x,y});
    visited[x][y] = 1;
    
    while(!q.empty()){
        int dx = q.front().first;
        int dy = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int mx = dx + dir[i][0];
            int my = dy + dir[i][1];
            if(mx >= 0 && mx < n && my >= 0 && my < m){
                if(visited[mx][my] == 0 && copy_map[mx][my] == 0){
                    visited[mx][my] = 1;
                    copy_map[mx][my] = 2;
                    q.push({mx,my});
                }
            }
            
        }
        
    }
    
}
    
    
void dfs(int idx,int cnt){
    
    if(cnt == 3){
        memset(visited, 0, sizeof(visited));
        // 기존의 맵을 변경시키면 안되기때문에 값을 카피시켜줍니다.
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                copy_map[i][j] = map[i][j];
            }
        }
        
        // 벽을 세우기 하나의 경우마다의 벽을 세워야함.
        int count = 0;
        for(int i=0; i<empty_size; i++){
            if(count == 3){
                break;
            }
            if(check[i] == 1){
                int x = empty[i].first;
                int y = empty[i].second;
                copy_map[x][y] = 1;
                count +=1;
            }
        }
        
        // virus 전염시키기
        for(int i=0; i<virus.size(); i++){
            int x = virus[i].first;
            int y = virus[i].second;
            bfs(x,y);
        }
        
        int safe_size = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(copy_map[i][j] == 0){
                    safe_size++;
                }
            }
            
        }
        
        if(ans < safe_size){
            ans = safe_size;
        }
        return;
    }
    
    // 조합의 형식으로 3개가 뽑힐때까지 뽑았다가 종료되는 시점에 그 값을 다시 false로 만들고 다시 조합의 경우를 뽑습니다.
    for(int i=idx; i<empty_size; i++){
        if(check[i] == 1){
            continue;
        }
        check[i] = 1;
        dfs(i, cnt+1);
        check[i] = 0;
    }
    
}
int main(void){
    cin >> n >> m;
    
    // 값을 입력받고 빈칸과 바이러스의 좌표를 담고 있는 벡터에 해당 값들을 넣어주게 된다.
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
            // 0: 빈칸
            if(map[i][j] == 0){
                empty.push_back({i,j});
            }
            // 2: 바이러스
            else if(map[i][j] == 2){
                virus.push_back({i,j});
            }
        }
    }
    // 빈칸을 기준으로 DFS를 수행한다. 따라서,조합의 경우라고 생각하면 됩니다. N(빈칸의 개수중)에서 3개를 뽑는 경우의 수라고 생각을 합니다.
    empty_size = empty.size();
    dfs(0,0);
    cout << ans;
    return 0;
}

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class 연구소 {
    static class Dot {
        private int x;
        private int y;
        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int n;
    static int m;
    static int[][] map;
    static int[][] copy_map;
    static List<Dot> virusList = new ArrayList<Dot>();
    static int[][] dir ={{-1,0},{1,0},{0,1},{0,-1}};
    static int ans = 0;

    static void wallDfs(int idx, int cnt) {

        if(cnt == 3){
            // map Copy
            copyMapFunc();
            // virus spread
            for(Dot dot : virusList){
                virusSpreadBfs(dot.x, dot.y);
            }
            // safe Area
            ans = Math.max(ans, getSafeArea());
            return;
        }

        for(int i=idx; i<n * m; i++){
            int x = i / m;
            int y = i % m;
            if(map[x][y] == 1 || map[x][y] == 2){
                continue;
            }
            map[x][y] = 1;
            wallDfs(i+1, cnt+1);
            map[x][y] = 0;
        }
    }
    // 맵 카
    static void copyMapFunc() {
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                copy_map[i][j] = map[i][j];
            }
        }
    }
    // 바이러스 퍼트리기
    static void virusSpreadBfs(int x,int y) {
        for(int i=0; i<4; i++){
            int mx = x + dir[i][0];
            int my = y + dir[i][1];

            if(mx >= 0 && mx < n && my >= 0 && my < m){
                if(copy_map[mx][my] == 0){
                    copy_map[mx][my] = 2;
                    virusSpreadBfs(mx,my);
                }
            }
        }

    }
    // 안전영역 개수 체크
    static int getSafeArea() {
        int safe = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(copy_map[i][j] == 0){
                    safe += 1;
                }
            }
        }
        return safe;
    }

    /*
    4 6
    0 0 0 0 0 0
    1 0 0 0 0 2
    1 1 1 0 0 2
    0 0 0 0 0 2
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        copy_map = new int[n][m];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2){
                    virusList.add(new Dot(i,j));
                }
            }
        }
        wallDfs(0,0);

        System.out.println(ans);
    }
}

AlgorithmSW역량테스트

1. 문제 링크

2. 문제 조건

3. 컴퓨팅 사고

3.1. 다시 풀어보았습니다.

4. 풀이 코드