P.14502 연구소

코드

package Baekjoon.Class;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class P_14502 {

    static int n, m;
    static int[][] map;
    static ArrayList<Virus> viruses;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int ans = 0;

    static class Virus {
        int x, y;

        public Virus(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; m = line[1];
        viruses = new ArrayList<>();
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 2) viruses.add(new Virus(j, i));
            }
        }

        solve(0);

        bw.write(Integer.toString(ans));
        bw.flush();
    }

    private static void solve(int cnt) {
        if (cnt == 3) bfs();
        else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        solve(cnt + 1);
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

    private static void bfs() {
        LinkedList<Virus> queue = new LinkedList<>(viruses);
        boolean[][] visited = new boolean[n][m];
        int[][] copyMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) copyMap[i][j] = map[i][j];
        }

        while (!queue.isEmpty()) {
            Virus poll = queue.poll();

            if (!visited[poll.y][poll.x]) {
                visited[poll.y][poll.x] = true;

                for (int i = 0; i < 4; i++) {
                    int nextX = poll.x + dx[i];
                    int nextY = poll.y + dy[i];

                    if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextY][nextX] && copyMap[nextY][nextX] == 0) {
                        copyMap[nextY][nextX] = 2;
                        queue.add(new Virus(nextX, nextY));
                    }
                }
            }
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyMap[i][j] == 0) cnt++;
            }
        }

        ans = Math.max(ans, cnt);
    }
}

코드 설명

백트래킹과 bfs를 합친 문제이다.

 

순서는 다음과 같다.

1. 3개의 벽을 세운다.
2. 안전 지대를 계산한다.

 

1번은 백트래킹을 이용했다.

private static void solve(int cnt) {
    if (cnt == 3) bfs();
    else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    solve(cnt + 1);
                    map[i][j] = 0;
                }
            }
        }
    }
}

백트래킹을 할 때마다 [0][0]을 참조해야해서 시간을 좀 버리게 됐는데 최대 맵의 크기가 8x8임을 생각하면 큰 시간이 걸릴 것 같진 않다.

 

벽을 세개 세웠다면 (cnt == 3) bfs를 통해 2번을 수행했다.

while (!queue.isEmpty()) {
    Virus poll = queue.poll();

    if (!visited[poll.y][poll.x]) {
        visited[poll.y][poll.x] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = poll.x + dx[i];
            int nextY = poll.y + dy[i];

            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextY][nextX] && copyMap[nextY][nextX] == 0) {
                copyMap[nextY][nextX] = 2;
                queue.add(new Virus(nextX, nextY));
            }
        }
    }
}

새로운 맵 배열을 생성해 감염되었다면 2로 바꾸어주었다.

기존 맵을 사용한다면 다시 백트래킹으로 0으로 바꾸어주는 과정을 거쳐야하기 때문에 더 복잡하다.

 

새로운 맵 배열을 생성하는 것은 깊은 복사로 한다.

얕은 복사로 생성할 경우 copyMap을 수정할 때 기존의 map도 바뀌게 된다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) copyMap[i][j] = map[i][j];
}

 

bfs 이후에는 copyMap을 순회하며 0의 개수를 세어 안전지대의 넓이를 업데이트해준다.