백준 18405번 경쟁적 전염

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Competitive_Spread {
    static int N,K;
    static int[] dr = {1,0,-1,0};
    static int[] dc = {0,1,0,-1};
    static int[][] map;

    static List<int[]> list;
    static int[] answer;


    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());
        map = new int[N][N];
        answer = new int[3];
        list = new ArrayList<>();

        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){
                    list.add(new int[]{map[i][j],i,j,0});
                }
            }
        }
        Collections.sort(list,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0],o2[0]);
            }
        });


        st = new StringTokenizer(br.readLine());
        answer[0] = Integer.parseInt(st.nextToken());
        answer[1] = Integer.parseInt(st.nextToken());
        answer[2] = Integer.parseInt(st.nextToken());
        bfs();
        System.out.println(map[answer[1]-1][answer[2]-1]);

    }
    public static void bfs(){
        Queue<int[]> que = new LinkedList<>();
        for (int[] ints : list) {
            que.add(ints);
        }
        while (!que.isEmpty()){
            int[] current = que.poll();
            int virusnum = current[0];
            int crow = current[1];
            int ccol = current[2];
            int time = current[3];
            if(time==answer[0]) return;
            for (int i = 0; i < 4; i++) {
                int nrow = crow + dr[i];
                int ncol = ccol + dc[i];
                if(nrow<0||ncol<0||nrow>=N||ncol>=N)
                    continue;
                if(map[nrow][ncol]==0){
                    map[nrow][ncol] = virusnum;
                    que.add(new int[]{virusnum,nrow,ncol,time+1});
                }
            }
        }

    }
}

문제 조건

바이러스 종류가 1인것부터 K번 인것까지 순차적으로 전염.
1초에 한칸씩 전염될때, x초에 해당하는 전염상태를 구하라

풀이 방법

처음 입력받을때 바이러스의 종류가 1번인것 부터 que에 순차적으로 넣어야 나중에 bfs수행했을때, 번호순으로 순차적으로 전염된다.
따라서 처음que에 바이러스를 넣는 순서가 중요하다.

1. 바이러스에 해당하는 좌표와 바이러스 종류를 list에 담는다.
2. list를 정렬한다. 📢Collection.sort(list,Comparator<>())를 활용하여 바이러스 종류를 기준으로 오름차순 정렬한다.
3. bfs()탐색을 시작한다.
4. 바이러스 종류를 기준으로 순차적으로 담긴 list를 que에 담는다.
5. map이 0일 경우에만 전염을 시켜주고, 📢전염된 좌표,바이러스 종류, 시간+1을 같이 que에 넘겨준다.
6. que에서 꺼낸 시간이 x초가 될때 탈출하고 해당 좌표를 출력한다.

후기

처음 설계할때 초가 1초씩 증가할때마다 바이러스 종류 별로 bfs가한번만 동작하도록 구성하였다.
for문이 너무 많아져서 시간초과 오류가 났다.
다시 설계할때 정렬해서 que에 넣는것을 떠올리긴했는데 또 Comparator 사용법이 익숙치 않아서 포기했다.
Comparator를 사용한뒤에도 시간 증가를 어떻게 처리해야 할지 몰랐는데 큐에 time을 같이 넣어줌으로써 해결하는 방법을 사용했다.
이 방법도 예전에 한번 해봤는데 익숙치 않아서 못 떠올렸던것 같다.

1. 일정 인덱스를 기준으로 정렬하는 Comparator 사용법
2. time을 큐에 하나씩 증가시켜서 넣는 방법

두가지를 익숙하게 사용할줄 알아야겠다.