백준 18405번 : 경쟁적 전염 java

이 문제는 우선순위 큐를 이용하여 입력을 받아준 후 bfs를 이용하면 되는 문제입니다.

이 문제에서는 N x N 크기의 시험관에서 K종류의 바이러스가 존재한다고 합니다.

그리고 이 바이러스는 숫자가 낮은 바이러스부터 차례대로 주변으로 한 칸씩 증식합니다.

이때 바이러스가 증식하는 순서를 정렬하기 위해서 PriorityQueue를 사용해줍니다.

그리고 각 초마다 증식하기 때문에 각 초마다 주변으로 1칸씩 우선순위 큐에 들어있는 순서대로 증식하게 만듭니다.

그리고 (3, 2) 칸에 바이러스가 존재한다면 바로 종료하도록 만들었습니다.

바로 코드를 보여드리도록 하겠습니다.

---

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

public class Main {
    static int N;
    static int[][] map;
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};

    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());
        int K = Integer.parseInt(st.nextToken());

        map = new int[N+1][N+1];

        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());
        }

        st = new StringTokenizer(br.readLine());

        int time = Integer.parseInt(st.nextToken());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());

        while(time-->0){
            if(map[row][col] != 0)
                break;

            diffusion();
        }

        System.out.println(map[row][col]);
    }

    static void diffusion(){
        Queue<Node> q = new PriorityQueue<>();
        boolean[][] visited = new boolean[N+1][N+1];

        for(int i = 1; i<=N; i++){
            for(int j = 1; j<=N; j++){
                if(map[i][j] != 0){
                    visited[i][j] = true;
                    q.offer(new Node(i, j, map[i][j]));
                }
            }
        }

        while(!q.isEmpty()){
            Node a = q.poll();

            for(int i = 0; i<4; i++){
                int dr = a.row + dR[i];
                int dc = a.col + dC[i];

                if(dr<1||dc<1||dr>N||dc>N)
                    continue;
                if(visited[dr][dc])
                    continue;

                map[dr][dc] = a.val;
                visited[dr][dc] = true;
            }
        }
    }
}
class Node implements Comparable<Node>{
    int row, col, val;

    Node(int row, int col, int val){
        this.row = row;
        this.col = col;
        this.val = val;
    }

    @Override
    public int compareTo(Node a){
        return this.val - a.val;
    }
}

우선순위 큐를 이용하여 bfs를 진행해주면 되는 문제였습니다.