0. PriorityQueue 사용

• PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.
• Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다.

참고 사이트
https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

1. 문제

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

2. 풀이

1. 먼저 PriorityQueue로 바이러스 순서에 맞게 넣어준다. (매초마다 번호가 낮은 종류의 바이러스부터 증식하기 때문)

2. PriorityQueue에 있는 값을 Queue에 넣어준다.

3. 매 초마다 Queue size를 파악하여 그만큼만 꺼내서 4방향으로 증식을 진행한다.

3. 코드

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

public class Main{
    public static class Node implements Comparable<Node>{
        int x;
        int y;
        int num;
        
        public Node(int x, int y, int num){
            this.x = x;
            this.y = y;
            this.num = num;
        }
        
        @Override
        public int compareTo(Node other){
            return Integer.compare(this.num, other.num);
        }
    }
    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];
        int moveX[] = {1, -1, 0, 0};
        int moveY[] = {0, 0, 1, -1};
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Queue<Node> q = new LinkedList<>();
        
        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){
                    pq.add(new Node(i, j, map[i][j]));
                }
            }
        }
        
        while(!pq.isEmpty()){
            q.add(pq.poll());
        }
        
        st = new StringTokenizer(br.readLine(), " ");
        int S = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken()) - 1;
        int Y = Integer.parseInt(st.nextToken()) - 1;
        
        while(S > 0){
            int qSize = q.size();
            for(int i = 0; i < qSize; i++){
                Node node = q.poll();
                for(int j = 0; j < 4; j++){
                    int goX = node.x + moveX[j];
                    int goY = node.y + moveY[j];
                    
                    if(goX < 0 || goY < 0 || goX >= N || goY >= N){
                        continue;
                    }
                    if(map[goX][goY] != 0){
                        continue;
                    }
                    
                    map[goX][goY] = node.num;
                    q.add(new Node(goX, goY, map[goX][goY]));
                }
            }
            S -= 1;
        }
        System.out.println(map[X][Y]);
    }
}