[자바] 백준 24513 - 좀비 바이러스 (boj java)

문제 : boj24513

 

  문제를 풀 개념만 확실히 잡는다면, 그 이후로는 구현력에 달려 있는 문제이다. 구현이 상당히 복잡할 수 있다. 구현자체는 코드를 참고해서 짜보고, 일단 개념만 풀이로 작성해보겠다.

 

  이하의 예시를 생각해보자.

3 3
1 0 0
0 0 0
0 0 2

우선 1번 바이러스가 전체 맵을 진행할 때, 각 마을에 도착하는 시간을 재보면 다음과 같을 것이다.

 

그 다음 2번 바이러스가 차례차례 1번 바이러스의 지점들을 덮으면서 진행해보자.

 

  위에서 동일한 거리끼리 만나게 되었다. 즉, 해당 지점에 각 바이러스는 동일한 시각에 도착한다는 의미이다. 따라서 이 지점에서 3번 바이러스가 만들어지게 되는 것이다. 최종적으로 각 마을마다 감염되는 바이러스의 번호는 다음과 같다.

 

--------------

 

  이번엔 다음의 예시를 생각해보자.

3 3
1 0 0
0 0 2
0 0 0

 

마찬가지로 우선 1번 바이러스로 진행한 거리는 다음과 같다.

이번에도 2번 바이러스로 덮으면서 진행해보자.

  이번엔 서로 동일한 거리가 생기지 않는다. 이 때, 진행 과정에서 볼 수 있듯이 2번으로 덮을 때 자신보다 거리가 더 긴 곳은 덮어버렸고, 다음칸이 현재칸과 동일한 곳에 대해서는 더이상 진행하지 못했다. 이건 해당 마을에 동시에 도착하지 않았지만, 해당 바이러스가 더 먼저 도착했으므로 더 진행하지 못하는걸 의미한다. 최종적으로 각 마을의 바이러스 분포는 다음과 같다.

 

  그렇다면 바이러스 1번을 전체에 대해 진행하고 -> 2번을 진행하면서 동일한 위치에 동일한 거리로 도착했다면 바이러스 3으로 변경, 동일한 거리에 1번이 먼저 도착했다면 진행 못함, 2번이 먼저 도착했다면 바꿔버리기. 이런식으로 진행하면 2번의 bfs로 구해낼 수 있을거라 예상할 수 있다.

 

-------------------

 

   이번엔 이걸 생각해보자.

4 4
1 0 2 -1
-1 0 -1 0
0 0 0 0

 

이 경우, 위 처럼 진행한다면 최종적으로 각 마을의 바이러스 분포는 다음과 같이 될 것이다.

  이게 문제인데, 이걸  처리하기 위해서는 결국 위에서 설명한 대로 진행하려면 다음과 같이 해야 한다.

 

1. 바이러스 1번으로 전체 bfs 진행하면서 도달할 수 있는 곳들에 1번 바이러스 지역임을 명시한다.

2. 바이러스 2번으로 위에서 설명했던 로직대로 진행하면서 2번 바이러스 지역임을 명시한다.

3. 바이러스 1번에서 다시 bfs를 진행하면서, 2번 바이러스 지역이나 3번 바이러스 지역이 나오는 부분까지로 1번 지역을 제한해야 한다. 

 

이러면 bfs가 총 3번이 필요하고, 시간 초과가 날 가능성이 있다.

 

-----------

 

  위에서 설명했던 개념이 이해되었다면 사실 bfs를 동시에 진행해도 상관없다. 즉 큐에 맨 처음에 1번 바이러스 시작지점과 2번 바이러스 시작점을 둘 다 넣고 동시에 진행하는 것이다. 서로 어느 바이러스의 객체인지만 잘 명시하면 된다(코드의 type). 코드를 참고해보자. 설명이 없으면 잘 이해안될만한 부분은 다음과 같다.

 

- type은 0이 1번바이러스, 1이 2번바이러스를 뜻한다. 따라서 '1-type'은 1번이면 2번바이러스, 2번이면 1번바이러스를 의미한다. 즉 상대 바이러스를 뜻한다.

 

- for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (((dr ^ dc) & 1) != 1) continue;

요 부분은 일반적으로 bfs 진행 시 int[] dr = {1, 0, 0, -1}; int[] dc = {0, 1, -1, 0}; 과 같이 상하좌우 방향 지정해주는 부분을 비트 연산으로 해준 것이다. 별 의미 없다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Pos {
    int r, c, type;
    public Pos(int r, int c, int type) {
        this.r = r;
        this.c = c;
        this.type = type;
    }
}
public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int[][] answer = new int[r][c];
        int[][][] map = new int[2][r][c];
        for (int i = 0; i < 2; i++) for (int j = 0; j < r; j++) Arrays.fill(map[i][j], Integer.MAX_VALUE);
        Queue<Pos> q = new ArrayDeque<>();
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                switch (Integer.parseInt(st.nextToken())) {
                    case -1 : answer[i][j] = -1; break;
                    case 1 : q.add(new Pos(i, j, 0)); answer[i][j] = 1; map[0][i][j] = 1; break;
                    case 2 : q.add(new Pos(i, j, 1)); answer[i][j] = 2; map[1][i][j] = 1; break;
                }
            }
        }
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            if (answer[cur.r][cur.c] == 3) continue;
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (((dr ^ dc) & 1) != 1) continue;
                    int nr = cur.r+dr;
                    int nc = cur.c+dc;
                    int type = cur.type;
                    if (nr<0||nr>=r||nc<0||nc>=c||answer[nr][nc]==-1||map[type][nr][nc]!=Integer.MAX_VALUE) continue;
                    int nd = map[type][cur.r][cur.c]+1;
                    if (map[1-type][nr][nc]==nd) {
                        answer[nr][nc] = 3;
                        continue;
                    }
                    if (map[1-type][nr][nc]<nd) continue;
                    answer[nr][nc] = type+1;
                    map[type][nr][nc] = nd;
                    q.add(new Pos(nr, nc, type));
                }
            }
        }
        int[] cnt = new int[4];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (answer[i][j] >= 1)
                    cnt[answer[i][j]]++;
            }
        }
        System.out.println(String.format("%d %d %d", cnt[1], cnt[2], cnt[3]));
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}