[백준] 14502. 연구소

문제 출처

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

문제 설명

2차원 좌표계에 벽과 바이러스가 있다.

바이러스는 확산되지만 벽은 통과할 수 없다.

3개의 벽을 더 세워서 바이러스를 최대한 억제해라.

문제 풀이

지도가 최대 8x8로 아담하다.

3개의 벽을 세울 수 있는 모든 경우의 수를 도전해봐도 충분할 것이다.

3개의 벽을 세웠다면 바이러스를 확산시키고 안전 구역을 센다.

안전 구역의 최댓값을 출력한다.

 

왜 모든 경우의 수를 도전해봐도 충분한가?

최악의 경우 8x8에 3개의 벽을 세울 수 있는 경우의 수는 64C3 = 41,664 이고

8x8의 지도를 41,664번 순회한다면 2,666,496회의 연산이 필요하다.

이런 식의 어림짐작으로 1억을 넘지않는다면 백준의 1초를 통과할 수 있다.

이 계산법은 백준의 까다로운 시간 제한에 맞추는데 어느 정도 신뢰성 있는 추정 방법이다.

코드

코드 해설

    public static void main(String[] args) throws IOException {
        readInput();
        answer = 0;
        dfs(0, -1, 0);
        System.out.println(answer);
    }

메인문은 언제나 심플하게.

1. 입력을 받는다.

2. 계산한다.

3. 답을 출력한다.

 

    public static void dfs(int r, int c, int wallCount) {
        if (wallCount >= 3) {
            int[][] mapClone = activateVirus();
            int safeZoneCount = getSafeZoneCount(mapClone);
            // if (answer < safeZoneCount) {
            //     System.out.println("**** " + safeZoneCount + " ****");
            //     printMap(mapClone);
            // }
            answer = Math.max(answer, safeZoneCount);
        } else {
            int cc = c + 1;
            for (int cr = r; cr < N; cr++) {
                for (; cc < M; cc++) {
                    if (map[cr][cc] == 0) {
                        map[cr][cc] = 3;
                        dfs(cr, cc, wallCount + 1);
                        map[cr][cc] = 0;
                    }
                }
                cc = 0;
            }
        }
    }

dfs() 는 3개의 벽을 세울 모든 경우를 시도한다.

최대 64개의 칸 중 중복되지 않게 3개의 칸을 뽑는 모든 경우의 수를 계산한다.

벽을 세울 칸을 뽑을 땐 3이라는 값을 넣어주고 다음 벽을 고르기위해 dfs() 를 재귀적으로 호출한다.

3개를 뽑고나면 activateVirus() 가 지도에 바이러스를 확산시킨다.

확산 후에는 getSafeZoneCount() 가 지도의 안전 구역을 센다.

더 많은 안전 구역을 확보하는 경우를 찾았다면 그 답을 출력한다.

 

    public static int[][] activateVirus() {
        Queue<int[]> queue = new LinkedList<>();
        int[][] mapClone = new int[N][M];
        for (int r = 0; r < N ; r++) {
            for (int c = 0; c < M; c++) {
                mapClone[r][c] = map[r][c];
                if (map[r][c] == 2) {
                    queue.offer(new int[] {r, c});
                }
            }
        }
        final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] d : dirs) {
                int[] next = new int[] {cur[0] + d[0], cur[1] + d[1]};
                if (0 <= next[0] && next[0] < N && 0 <= next[1] && next[1] < M && mapClone[next[0]][next[1]] == 0) {
                    queue.offer(next);
                    mapClone[next[0]][next[1]] = 4;
                }
            }
        }
        return mapClone;
    }

activateVirus() 는 바이러스를 확산시킨다.

확산하기 전에 지도를 복사하여 mapClone이라는 임시 지도에 확산하도록 했다.

( 지도에 직접 확산 시키고 확산을 다시 지우는 방법도 있다 )

초기 바이러스를 모두 큐에 넣는다.

큐에 있는 바이러스들은 네 방향으로 확산한다.

확산할 때 벽이거나 이미 바이러스인 쪽은 가지 않는다.

큐가 비었다면 확산도 끝이다.

 

    public static int getSafeZoneCount(int[][] mapClone) {
        int count = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                count += mapClone[r][c] == 0 ? 1 : 0;
            }
        }
        return count;
    }

지도의 모든 안전 구역을 세서 돌려준다.