[14502] 연구소

Language

JAVA

Input

연구소 크기 N*M
연구소 현재 상태 (0: 빈칸, 1: 벽, 2: 바이러스)

Output

벽을 3개를 세웠을 때, 안전영역의 최댓값
(벽을 세운 후, 바이러스가 상하좌우로 더이상 못 퍼질 때 까지 퍼진다. 이후에도 바이러스가 퍼지지 않은 영역을 안전영역이라고 한다.)

문제 이해 및 풀이

• DFS와 BFS를 모두 이용한 문제이다.
  이 문제를 풀면, 두 개념 모두 어떻게 구현하는지 확실히 알 것같아 정리하기로 했다!

Algorithm

• 벽 3개를 세워준다. (DFS)
• 벽 3개를 모두 세웠으면, 바이러스를 퍼뜨려 준다.(BFS)
• 안정영역을 계산하고, 최댓값을 갱신해준다.

1) 벽을 세워주는 함수 check

public static void check(int cnt){
        if(cnt == 3){
            calcul();
            return;
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                //만약 빈 칸이라면 벽을 세워본다.
                if(board[i][j] == 0){
                    board[i][j] = 1;
                    check(cnt+1);
                    board[i][j] = 0;
                }
            }
        }

    }

- 세운 벽의 수가 3개라면 바이러스를 퍼뜨리는 함수인 calcul로 옮겨준다.
- 각 칸을 돌아가며, 빈 칸일 경우 벽을 세워준다.
- 백트래킹을 위하여 check가 return된 다음에는 세운 벽을 허물어 준다.

2) 바이러스를 퍼뜨려주고 안정영역을 계산하는 함수 calcul

Queue<pair> q = new LinkedList<>();

        for(int i = 0; i <N; i++){
            for(int j = 0; j < M; j++){
                if(board[i][j] == 2) q.add(new pair(i,j));
            }
        }

        tmp = new int[N][M];
        for(int i = 0; i < N; i++) tmp[i] = board[i].clone();

        while(!q.isEmpty()){
            pair now = q.poll();

            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                //out of boundary 거나 벽이면 continue
                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if(tmp[nx][ny] == 1 || tmp[nx][ny] == 2) continue;

                //만약 빈 칸이면 바이러스를 퍼뜨려 준다.
                tmp[nx][ny] = 2;
                q.add(new pair(nx,ny));
            }
        }
        
    - Queue에 초기에 바이러스 위치를 넣어준다.
    - 해당 바이러스를 상하좌우로 퍼뜨리고, 퍼뜨릴 수 있다면 그 위치를 다시 q에 넣어준다.

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

        ans = Math.max(ans,result);

	- 바이러스를 모두 퍼뜨렸다면, 안전영역을 계산해준다.