[Algo] 백준 18405 경쟁적 전염 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/18405

메모리 : 22916KB

시간 : 292ms

언어 : Java 11

---

코드

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

public class Main {
    static class Node {
        int r, c, num, level;

        Node(int r, int c, int num, int level) {
            this.r = r;
            this.c = c;
            this.num = num;
            this.level = level;
        }
    }

    static int[][] vector = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][N];
        Queue<Node> q = new LinkedList<>();
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {

            @Override
            public int compare(Node o1, Node o2) {
                return o1.num - o2.num;
            }

        });
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] != 0) {
                    q.add(new Node(i, j, map[i][j], 0));
                }
            }
        }
        st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        int now = 0;
        while (!q.isEmpty() && S != now) {

            while (!q.isEmpty() && q.peek().level == now) {
                pq.add(q.poll());
            }
            now++;

            while (!pq.isEmpty()) {
                Node n = pq.poll();
                for (int k = 0; k < 4; k++) {
                    int x = n.r + vector[k][0];
                    int y = n.c + vector[k][1];
                    if (x >= 0 && y >= 0 && x < N && y < N && map[x][y] == 0) {
                        map[x][y] = n.num;
                        q.add(new Node(x, y, n.num, n.level + 1));
                    }
                }
            }
        }
        System.out.println(map[X - 1][Y - 1]);
    }
}

풀이

두 가지 조건을 지키는 bfs이다.

1. 번호가 낮은 바이러스부터 확산된다.
2. 이미 바이러스가 있는 칸에는 확산되지 않는다.

모든 바이러스를 queue에 넣고, 같은 시점에 퍼지는 것들을 pq에 넣어 낮은 번호 순으로 정렬한다.

여담으로 오타를 내서 디버깅에 시간을 한참 썼다. 근데도 테케는 통과를 했어서ㅋㅋ 오타에 신경쓰자.