BFS + Backtracking 으로 연구소 풀기 (백준 14502. 연구소)

문제 분석

0 빈 칸

1 벽

2 바이러스

• 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
• 새로 세울 수 있는 벽의 개수는 3개이며 꼭 3개를 세워야 한다.
• 바이러스의 확산을 막기 위해 가장 효과적으로 벽을 세워야 한다.
• 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 

풀이

1. backtracking 으로 벽 3개를 세우는 조합을 구한다.
2. 벽 3개를 세웠을 때, BFS 로 바이러스를 최대한 퍼뜨린다.
3. 그 상황에서 안전 영역을 세고, backtracking 함수 에서 min 값을 구한다.

Backtracking 함수 구현

역할: 벽을 3개 세우는 조합을 구한다.

depth 는 지금까지 구한 벽의 개수!!

static void backtracking(int depth) {
    if (depth == 3) {
        ans = Math.max(ans, bfs());
        return;
    }

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

BFS 함수 구현

역할: 상하좌우를 탐색하면서 바이러스를 퍼뜨리고, 안전 영역 개수를 센다.

BFS 함수는 벽 3개의 조합을 구했을 때만 돈다.

int[][] copy = new int[N][M];

for (int i = 0; i < N; i++) {
    copy[i] = map[i].clone();
}

Queue<Point> q = new ArrayDeque<>();

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (copy[i][j] == 2) {
            q.offer(new Point(i, j)); // 지금 바이러스가 있는 칸 큐에 넣기
        }
    }
}

1. BFS 로 바이러스를 퍼뜨리면, static 으로 선언한 map 자체가 변하기 때문에 copy 로 map 복사본을 만들어준다.
2. 퍼져나갈 바이러스를 모두 저장할 q 를 선언한다.
3. 지금 바이러스가 있는 칸을 큐에 넣는다

함수에 좌표를 계속 사용해줘야 하기 때문에, 좌표 값을 Point 클래스로 선언해두고 사용한다.

• q.offer(value): 삽입
• q.poll(): 삭제 -> 삭제된 value 반환

// 바이러스 퍼뜨리기
while (!q.isEmpty()) {
    Point cur = q.poll();

    for (int i = 0; i < 4; i++) {
        int nr = cur.r + dx[i];
        int nc = cur.c + dy[i];

        if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
            if (copy[nr][nc] == 0) {
                copy[nr][nc] = 2;
                q.offer(new Point(nr, nc));
            }
        }
    }
}

1. 상하좌우 탐색을 하면서 빈 칸인 경우에 2 로 바꿔 바이러스를 퍼뜨린다. 
2. 맨 처음에 있던 바이러스 이후로도 계속 새로운 바이러스가 생겼을 때마다 q 에 바이러스를 넣어주기 때문에 q 가 빌 때까지 반복한다면 모든 바이러스 전파를 체크할 수 있다.

int safe = 0;
// 안전 영역 세기
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (copy[i][j] == 0) {
            safe++;
        }
    }
}

return safe;

모두 돌고 난 후의 안전 영역을 세고, backtracking 함수에서 min 값을 가려낸다. 

DFS (재귀) 구현 코드

// 바이러스 전파를 시작하는 함수
static int dfs() {
    int[][] copy = new int[N][M];
    for (int i = 0; i < N; i++) {
        copy[i] = map[i].clone();
    }

    // 모든 바이러스 위치에서 재귀 시작
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (copy[i][j] == 2) {
                recursive(i, j, copy);
            }
        }
    }

    // 안전 영역 카운트
    int safe = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (copy[i][j] == 0) safe++;
        }
    }
    return safe;
}

// 상하좌우로 뻗어나가는 재귀 함수
static void recursive(int r, int c, int[][] copy) {
    for (int i = 0; i < 4; i++) {
        int nr = r + dx[i];
        int nc = c + dy[i];

        // 범위 내에 있고, 빈칸(0)인 경우만 전파
        if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
            if (copy[nr][nc] == 0) {
                copy[nr][nc] = 2; // 방문 처리 겸 바이러스 표시
                recursive(nr, nc, copy); // 다음 칸으로 이동
            }
        }
    }
}

DFS (재귀) vs BFS

BFS 는 가까운 곳부터 넓게 퍼져 나가는 방식이고 DFS 코드는 한 방향으로 끝까지 갔다가 돌아오는 방식이다. DFS 코드는 바이러스 칸일 경우에 자기 자신을 계속 호출하면서 쌓아 올리다가 더 갈 곳이 없으면 위에서부터 하나씩 치우면서 돌아온다. (맵이 커질 경우 스택 오버 플로우 발생 가능)