[백준 / Java] 14502: 연구소 (백트래킹, BFS)

난이도: Gold 4

문제: https://www.acmicpc.net/problem/14502

 

 

세로: N, 가로: M인 N * M 행렬이 있다.

 

 

3개의 벽(1)을 임시로 둔다.

 

 

바이러스(2)가 벽(1)을 제외하고 상하좌우로 퍼진다.

 

 

바이러스가 퍼지지 않은 구역은 남은 0의 개수를 세어 보면 된다.

총 27개가 나온다.

 

 

바이러스가 최소한으로만 퍼지게, 즉 안전 영역의 개수가 최대한 많게 3개의 벽을 세워야 한다.

 

N, M의 최대 개수가 8인 것을 보면 시간 복잡도에 전혀 영향을 끼치지 않는다.

벽을 3번 세우려면 최소 6중 for문을 돌려야 할 것 같은데,

8 * 8 * 8 * 8 * 8 * 8 = 262,144인 것을 보면 정말 시간 복잡도를 신경 쓰지 않아도 된다.

 

3개의 벽을 세우기 위해서는 브루트포스로 모든 경우의 수를 찾아봐야 한다.

 

1 0 1

0 0 2

0 2 0

 

예를 들어, 초기 단계를 위와 같다고 치자.

 

3개의 벽을 세우는 경우의 수는 정말 모두 일일히 찾아봐야 한다.

 

1 1 1

1 1 2

0 2 0

 

1 1 1

1 0 2

1 2 0

 

1 1 1

1 0 2

0 2 1

 

1 1 1

0 1 2

1 2 0

 

...

 

이런 식으로 임시로 둔 1이 맨 오른쪽에 있던 것부터 2중 for문을 돌리고,

맨 오른쪽에 있던 1이 맨 끝 좌표로 가면

중간에 있던 1을 오른쪽으로 1칸 옮기고 다시 맨 오른쪽에 있던 1을 돌리고....

이것의 반복이다.

 

즉, 

for (1~N)

    for (1~M)

          for (1~N)

               for (1~M)

                    for (1~N)

                         for (1~M)

 

인 것이다.    

 

그리고 3개의 벽을 임시로 두면, 원래 0이었던 곳이 1로 바뀌게 된다.

저 작업을 끝내주면 다시 0으로 바꿔야 한다.

 

즉,

matrix[i][j] = 1

dfs(depth + 1)    // 이 작업을 3번 해주고 함수가 끝나면

matrix[i][j] = 0    // 다시 원상복구 시켜주어야 한다.

 

이것이 바로 백트래킹이다.

 

바이러스를 상하좌우로 퍼뜨리는 것은 bfs로 하면 된다.

나는 바이러스가 퍼진 곳을 3으로 표시할 것이다.

 

자, 그럼 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class P14502_연구소 {
    static int N, M;                    // 행렬의 세로 크기, 가로 크기
    static int[] dx = {-1, 0, 1, 0};    // 상, 하 이동
    static int[] dy = {0, -1, 0, 1};    // 좌, 우 이동
    static int[][] matrix;              // 2차원 행렬 배열
    static boolean[][] visited;         // 2차원 방문 체크 배열
    static int maxCount;                // 안전 영역의 최대 크기
    
    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());    
        matrix = new int[N][M];
        
        // 2차원 행렬 초기화
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // N과 M의 크기가 작다. 
        // 이럴 경우에는 시간 복잡도 상관 없이 모든 경우의 수를 다 확인해 봐도 된다.
        
        dfs(0);
        
        System.out.println(maxCount);
    }
    
    public static void dfs(int depth) {
        if (depth == 3) {
            searchVirusZone();
            int count = getCountOfSafetyZone();
            maxCount = Math.max(maxCount, count);
            return;
        }
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][j] = 1;
                    dfs(depth + 1);
                    matrix[i][j] = 0;
                }
            }
        }
    }
    
    public static void searchVirusZone() {
        visited = new boolean[N][M];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && matrix[i][j] == 2) {
                    bfs(i, j);
                }
            }
        }
    }
    
    public static void bfs(int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a, b});
        visited[a][b] = true;
        
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for (int i = 0; i < 4; i++) {
                int x = now[0] + dx[i];
                int y = now[1] + dy[i];
                
                if (x < 0 || y < 0 || x >= N || y >= M) {
                    continue;
                }
                
                if (visited[x][y] || matrix[x][y] != 0) {
                    continue;
                }
                
                queue.add(new int[] {x, y});
                visited[x][y] = true;
                matrix[x][y] = 3;
            }
        }
    }
    
    public static int getCountOfSafetyZone() {
        int count = 0;
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == 0) {
                    count++;
                } else if (matrix[i][j] == 3) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        return count;
    }
}