[백준 14502 / java] 연구소

문제

14502번: 연구소 (acmicpc.net)

1. 바이러스는 상하좌우 인접한 빈 칸으로 퍼져나감
2. 벽은 반드시 3개 세워야 함
3. 0:빈칸, 1:벽, 2:바이러스
4. 2<= 2의 개수 <=10
벽을 3개 세웠을 때, 안전 영역 크기의 최댓값?

풀이

처음에는 바이러스가 최소로 퍼지도록 하려면 벽이 어떻게 세워져야 하는지 생각해보았다.

바이러스의 가장 인접한 영역에 벽이 생겨야 한다. 하지만 벽은 3개밖에 사용할 수 없다.

2(바이러스)의 상하좌우를 탐색하며 가장 가까운 1과 연결되도록 한다? 

 

음.. 일단 입력값의 범위가 작으므로 완전탐색을 고려해보자.

모든 경우를 다 고려하는 브루트포스는?

벽 3개를 세우는 경우의 수를 모두 고려하는 방법.
N*M = 최악의 경우 3*8 = 24개의 자리 중 세 가지 자리를 뽑는 경우의 수는 

24_C_3 = 24*23*22/3*2*1 = 12144 < 1억 이므로 완탐으로 풀이가 가능하다.

 

IDEA1)
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

1. (0,0)부터 차례로 0인지 탐색
2. (0,1)에서 0을 찾음 -> 임시 행렬을 복사하여 (0,1)에 1을 삽입
3. (0,1) 정보+임시 행렬을 인자로 넘기며 재귀
4. (0,1)부터 차례로 0인지 탐색
5. (0,2)에서 0을 찾음 ->임시 행렬을 복사하여 (0,2)에 1을 삽입
...
이건 안 될듯

 

IDEA2)
1. 0의 좌표를 모두 넣은 리스트를 만들어서 그 리스트를 3번 참조하는 조합을 생성함
(같은 리스트 3개로 조합을 만들어 depth=3의 그래프를 구성)
그리고 겹치지 않게 좌표를 3개 선택해야 하므로 백트래킹으로 조건을 달아줘야 함

조건: 이전에 선택된 좌표보다 뒤에 저장된 좌표를 선택해야 함 (벽이 세워질 자리가 겹치지 않기 위해)

즉,  dfs로 벽 세울 좌표를 찾는 것

 

(예시)

 

2. 좌표를 정할 때마다 그 자리에 1 삽입

-> 재귀함수로 현재까지 1을 삽입한 상태의 행렬(board), 현재 선택한 좌표의 리스트 인덱스(start), 현재까지 정한 좌표의 수(count)를 넘겨줌 

3. 세 좌표를 모두 정했다면(if count >= 3)

-> 벽이 세워진 부분을 고려하여 바이러스가 퍼지게 만듦 (expandViruse()) -> bfs

-> 바이러스가 퍼진 후 0이 몇 개 있는지 리턴 (countSafetyZone())

-> 리턴값과 max값을 비교해 max를 갱신

4. 1~3 과정을 반복

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] board;
    static List<Point> walls, virus;
    static Queue<Point> q = new LinkedList<>();
    static int max = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][M];
        walls = new ArrayList<>();
        virus = new ArrayList<>();

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] == 0)
                    walls.add(new Point(i, j));
                if(board[i][j] == 2)
                    virus.add(new Point(i, j));
            }
        }

        safetyZone(board, 0, 0);
        bw.write(max + " ");
        bw.close();
    }
    static void safetyZone(int[][] board, int start, int count){
        //3개의 자리를 모두 선택했다면 안전 영역의 크기 리턴
        if(count >= 3){
            int[][] tmpBoard;
            tmpBoard = expandVirus(board);
            int num = countSafetyZone(tmpBoard);
            if(max < num)
                max = num;
            return;
        }

        for(int i = start; i< walls.size(); i++){
            boolean[] check = new boolean[walls.size()];
            int[][] tmpBoard;
            Point p = walls.get(i);
            tmpBoard = deepCopy(board);
            tmpBoard[p.x][p.y] = 1;
            safetyZone(tmpBoard, i+1, count+1);
        }
    }

    static int[][] expandVirus(int[][] board){
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        boolean[][] check = new boolean[N][M];

        for(int i = 0; i< virus.size(); i++){
            Point p = virus.get(i);
            q.offer(p);
            check[p.x][p.y] = true;
            while(!q.isEmpty()){
                p = q.poll();
                for(int j=0; j<4; j++){
                    int nx = p.x + dx[j];
                    int ny = p.y + dy[j];

                    if(nx<0 || nx>=N || ny<0 || ny>=M)
                        continue;
                    if(board[nx][ny] == 1 || check[nx][ny])
                        continue;
                    board[nx][ny] = 2;
                    q.offer(new Point(nx, ny));
                    check[nx][ny] = true;

                }
            }
        }
        return board;
    }
    static int countSafetyZone(int[][] board){
        int count = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(board[i][j] == 0)
                    count++;
            }
        }
        return count;
    }
    static int[][] deepCopy(int[][] arr){
        int[][] result = new int[arr.length][arr[0].length];
        for (int i=0; i<arr.length; i++) {
            result[i] = arr[i].clone();
        }
        return result;
    }
}
class Point{
    int x, y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

Note

• 주어진 테스트 케이스 3개가 모두 통과됐지만 제출 시 틀렸다고 해서 질문 게시판에서 반례를 찾아 실행해봤다.

4 3

1 1 1

0 0 0

0 0 0

2 0 0

출력 : 6

정답 : 5

• 위 반례를 실행해보니 5가 나와야 하는데 6이 출력되었다.
• 먼저 코드를 훑어보니 전체적인 흐름에는 문제가 없어 보였다.
• 실행은 되지만 0의 개수가 잘못 출력된 것이므로, 벽이 이상한 조합으로 세워져서 최종적으로 0의 개수가 잘못 카운팅된 것이 아닐까 하는 생각이 들었다.
• 정확한 원인을 알기 위해 아래와 같이 breakpoint를 잡고 디버깅하며 board의 어떤 위치에 1이 들어가는지 추적해보았다.

static void safetyZone(int[][] board, int start, int count){
        //3개의 자리를 모두 선택했다면 안전 영역의 크기 리턴
        if(count >= 3){
            int[][] tmpBoard;
            tmpBoard = expandVirus(board);
            int num = countSafetyZone(tmpBoard);
            if(max < num) //breakpoint
                max = num;
            return;
        }

        for(int i = start; i< walls.size(); i++){
            boolean[] check = new boolean[walls.size()];
            int[][] tmpBoard;
            Point p = walls.get(i); //breakpoint
            tmpBoard = deepCopy(board);
            tmpBoard[p.x][p.y] = 1;
            safetyZone(tmpBoard, i+1, count+1); //breakpoint
        }
    }

• 역시 벽의 위치를 조합하는 부분이 문제였다.
• 반례의 0 위치를 차례로 1~8이라고 했을 때, 다음과 같은 조합으로 벽이 생성되었다.
• 123 124 125 126 127 128
• 13 134 135 136 137 138
• 143 14 145 146 147 148
• 153 154 156 157 158
• 표시한 부분은 나오면 안 되는 조합이다. 마지막으로 선택된 좌표보다 더 뒤에 있는 좌표만을 선택해야 하기 때문이다.
• safetyZone()을 재귀호출하면서 인자로 start+1을 넘겨주고 있었다.
• 마지막으로 선택된 좌표는 i였으므로, start+1을 i+1로 바꿔주니 정답처리되었다.