[백준 18405] 경쟁적 전염 [Java]

문제

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

 

---

풀이

N * N크기의 보드에서 번호가 낮은 바이러스부터 상하좌우로 증식한다.

이 때, S초 후 ( X, Y )에 위치한 바이러스를 출력하는 문제다.

우선 ( X, Y )에 시작부터 바이러스가 있을 수 있다. 확인 후 탐색을 진행하자.

    private static int bfs() {
        if (A[X - 1][Y - 1] != 0)
            return;

번호가 낮은 바이러스 먼저 증식해야 하기 때문에 바이러스를 찾아, 바이러스 번호에 대해 오름차순으로 정렬 후 큐에 담아주자.

        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] > 0) {
                    list.add(new int[]{i, j, 0, A[i][j]});
                }
            }
        }
        list.sort(Comparator.comparingInt(a -> a[3]));

        Deque<int[]> queue = new ArrayDeque<>(list);

다음 시간이 S초 이하일 때 까지 BFS를 통해 바이러스들을 증식 시키면 된다.

BFS 간 S 이후의 탐색은 불필요하므로 다음 시간이 S 이하일 때 까지만 큐에 담아주자.

초기 보드의 값은 바이러스의 번호 또는 0이 주어지기 때문에 만약 S초 후 바이러스가 없다 하더라도 그냥 ( X, Y )의 값을 출력해도 된다.

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            final int x = cur[0];
            final int y = cur[1];
            final int time = cur[2];

            for (int d = 0; d < 4; ++d) {
                final int nx = x + dx[d];
                final int ny = y + dy[d];
                if (isValid(nx, ny) && A[nx][ny] == 0) {
                    if (time + 1 <= S) {
                        A[nx][ny] = A[x][y];
                        queue.add(new int[]{nx, ny, time + 1});
                    }
                }
            }
        }
    }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/18405.java