[백준 14502번] 연구소 - BFS, DFS

 

백준 14502번 DFS, BFS를 같이 사용해야 풀 수 있는 문제이다.

 

문제를 보게 되면,

N * M 인 직사각형의 연구소가 있다. 여기서 연구소 각 칸은 1 * 1의 크기를 가지며 빈 칸, 벽으로 이루어진다. 
여기서 일부의 칸에는 바이러스가 존재하게 되고 바이러스는 상하좌우로 퍼져나갈 수 있다. 그러나 벽이 존재하는 칸으로는 퍼지지 못한다.
여기서 꼭 벽 3개를 세워서 가장 바이러스가 감염되지 않는 칸을 많이 나오게 하는 수를 찾는 문제이다.

연구소 문제로 처음에 벽을 어떻게 3개를 세워야할까 긴가민가해서 고민을 많이 했던 문제다.

 

다른 사람의 방법을 보기 위해 검색을 좀 해봤고,,

 

그 결과, 벽을 세우기 위해선 결국 DFS을 통해 완전 탐색이 필요하다는 것을 알게 됐다.

 

이후, 느낌을 알았고 세워진 벽에 대해 바이러스가 퍼지는 것을 BFS로 실행을 하고 바이러스가 감염되지 않은 구역을 카운트하면 된다는 것을 알게 되었다.

 

즉, 가장 어려웠던 부분은 처음 완전 탐색으로 3개의 벽을 세운다는 것을 생각해낸다는 것이었다.

 

DFS을 통해 모든 경우를 탐색하고 BFS을 거기에 대해 실행하면 시간초과가 날 것 같았지만,

생각보다 시간 제한이 널럴해서 시간 초과는 나지 않았다.

 

우선 소스코드를 살펴보면,

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BAEKJOON14502 {
    // N 세로, M 가로
    static int N, M;
    static int[][] map;
    static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    static int[][] tempMap;

    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        map = new int[N][M];
        tempMap = new int[N][M];

        for (int i = 0; i < N; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    copy();
                    tempMap[i][j] = 1;
                    dfs(1);
                    tempMap[i][j] = 0;
                }
            }
        }

        System.out.println(result);

    }

    static void copy() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                tempMap[i][j] = map[i][j];
            }
        }
    }

    static void dfs(int wallCount) {
        if (wallCount == 3) {
            bfs();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(tempMap[i][j] == 0) {
                    tempMap[i][j] = 1;
                    dfs(wallCount+1);
                    tempMap[i][j] = 0;
                }
            }
        }
    }

    static void bfs() {
        Queue<Integer> queueX = new LinkedList<>();
        Queue<Integer> queueY = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (tempMap[i][j] == 2) {
                    queueX.offer(j);
                    queueY.offer(i);
                }
            }
        }

        int[][] spreadMap = new int[N][M];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                spreadMap[i][j] = tempMap[i][j];
            }
        }

        while (!queueX.isEmpty()) {
            int tempX = queueX.poll();
            int tempY = queueY.poll();

            for (int i = 0; i < 4; i++) {
                int destX = tempX + dir[i][1];
                int destY = tempY + dir[i][0];

                if (destX < 0 || destX >= M || destY < 0 || destY >= N) continue;
                if (spreadMap[destY][destX] != 0) continue;

                spreadMap[destY][destX] = 2;
                queueX.offer(destX);
                queueY.offer(destY);
            }
        }

        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (spreadMap[i][j] == 0) count++;
            }
        }

        if (count > result) result = count;
    }
}

 

 

우선 DFS 탐색을 시작하는 부분을 보면,

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (map[i][j] == 0) {
            copy();
            tempMap[i][j] = 1;
            dfs(1);
            tempMap[i][j] = 0;
        }
    }
}

 

copy()을 실행한다.

 

여기서 DFS에서 만족하는 조건별로 퍼지는 바이러스를 맵에 표시해야하기 때문에 필수인 작업이다.

이후, 벽이 없는 장소에 벽을 세우고 DFS을 실행한다.

 

다음으로 DFS의 코드를 보면,

static void dfs(int wallCount) {
    if (wallCount == 3) {
    	bfs();
      	return;
     }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if(tempMap[i][j] == 0) {
                tempMap[i][j] = 1;
                dfs(wallCount+1);
                tempMap[i][j] = 0;
             }
        }
    }
}

완전 탐색을 위해, 벽이 없는 부분에 벽을 세워주고 재귀함수를 실행한다.

이후, 완전 탐색이 끝난 후 다시 없는 경우로 만들어주고 새롭게 재귀를 시작한다.

 

여기서 벽이 3개 세워진 경우 BFS을 실행하고 현재 연구소에 대해 바이러스가 퍼진 횟수를 카운트 할 수 있게 한 후 기록한다.

---

그럼 간단하게 단계를 나누어 보면 다음과 같습니다.

 

1️⃣DFS을 통해 벽을 3개 세우는 완전탐색 수행

 

2️⃣벽이 3개 세워진 경우에 대해 BFS 실행

 

3️⃣바이러스가 모두 퍼진 후, 안전영역의 총 개수 합산

 

4️⃣모든 경우에 대해 안전 영역의 합산이 끝난 경우 가장 많은 경우 출력

 

이렇게 4단계로 나누어서 이해할 수 있을 것 같아요.

 

 

어려운 문제였지만, 이런 유형의 혼합된 문제가 기존의 BFS보다 심도가 더 깊어서 좋은 문제인 것 같네요 🤗