[백준] 18405번 : 경쟁적 전염

18405번: 경쟁적 전염

---

[BFS + 우선순위 큐]

1초마다 낮은 번호의 바이러스부터 상하좌우 인접한 칸(단, 0인 곳)으로 한 칸씩 전염시킬 수 있으므로 우선순위 큐를 사용해 낮은 번호의 바이러스부터 퍼지게 한다.

 

그러려면 입력을 받을 때 모든 바이러스를 우선순위 큐에 넣는다.

 

그리고 s번의 루프를 수행하고, 각 루프마다 BFS를 실행하는데 일반적인 BFS는 다음 탐색할 정점을 동일한 큐에 저장하는데 반해, 이 문제에서는 다른 큐(tmpQ라고 지정)에 저장하도록 한다. 이는 1초씩 나누어 탐색을 진행해야 하므로 이처럼 나누어 놓았다.

 

현재 정점의 바이러스가 n번일 때 주변을 탐색을 하기위한 조건은

1) 범위를 넘지 않고

2) 숫자가 0인 곳

을 n으로 수정한다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Point{
        int y, x, v;

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

    static int n, k;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int[][] map = new int[201][201];
    static Queue<Point> Q = new PriorityQueue<>((a, b) -> a.v- b.v);

    static void BFS(){
        Queue<Point> tmpQ = new PriorityQueue<>((a, b) -> a.v - b.v);

        while(!Q.isEmpty()) {
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int v = p.v;

            for (int a = 0; a < 4; a++) {
                int ny = y + Y[a];
                int nx = x + X[a];

                if (ny < 1 || nx < 1 || ny > n || nx > n || map[ny][nx] != 0) continue;

                map[ny][nx] = v;
                tmpQ.add(new Point(ny, nx, v));
            }
        }
        Q = tmpQ;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());

            for(int j=1; j<=n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());

                if(map[i][j] != 0)
                    Q.add(new Point(i, j, map[i][j]));
            }
        }
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int endY = Integer.parseInt(st.nextToken());
        int endX = Integer.parseInt(st.nextToken());

        int time = 0;
        while(time++ != s)
            BFS();

        System.out.println(map[endY][endX]);
    }
}