[Algorithm] 경쟁적 전염

풀이

 

바이러스는 1번부터 순차적으로 번져간다.

순서대로 꺼내서 번지는 것을 생각하면 큐를 사용하는 것이 좋았음.

바이러스 정보를 담은 객체 (좌표와 어떤 바이러스인지) 를 1번부터 순서대로 큐에 나열한다.

그리고 꺼낼 때마다 전염 시킨다. (전염할 수 있는 조건에 맞게)

(중심에 있는 바이러스는 이미 주변으로 퍼졌기 때문에 더 퍼질 수 없으니 다시 넣을 필요 없다.)

 

종료 조건에서 시간에 따른 종료 조건에 맞게 종료한다.

시간은 1번부터 k번까지 다 전염시킨 후에 더해진다.

큐에서 꺼내올 값의 index가 다시 1이 된 경우 시간을 증가시킨다.

(peek()으로 확인하는데 큐가 NULL이면 NPE 발생하므로 먼저 비어있는지 확인하고 함)

import java.util.*;

class Virus implements Comparable<Virus>{
    private int index;
    private int x;
    private int y;

    public Virus (int index, int x, int y) {
        this.index = index;
        this.x = x;
        this.y = y;
    }

    public int getIndex() { return this.index; }
    public int getX() { return this.x; }
    public int getY() { return this.y; }

    public int compareTo(Virus other) {
        return Integer.compare(this.index, other.getIndex());
    }
}

public class Main {

    public static int n, k;
    public static int s, x, y;
    public static int[][] graph = new int[201][201];

    public static List<Virus> viruses = new ArrayList<Virus>();

    public static int[] dx = {0, -1, 0, 1};
    public static int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
                if (graph[i][j] != 0) {
                    viruses.add(new Virus(graph[i][j], i, j));
                }
            }
        }
        s = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        sc.close();

        Collections.sort(viruses);
        Queue<Virus> q = new LinkedList<>();
        for (int i = 0; i < viruses.size(); i++) {
            q.offer(viruses.get(i));
        }

        // s초가 되면 끝
        int time = 0;
        while (!q.isEmpty()) {
            if (time == s) break;
            Virus v = q.poll();
            
            for (int i = 0; i < 4; i++) {
                int nx = v.getX() + dx[i];
                int ny = v.getY() + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < n && graph[nx][ny] == 0) {
                    graph[nx][ny] = v.getIndex();
                    q.offer(new Virus(graph[nx][ny], nx, ny));
                }
            }
            // k번째까지 다 계산하고 다시 돌아갈 때, time++
            // q가 비어있으면 q.peek()에서 NE;
            if (!q.isEmpty() && (q.peek().getIndex() == 1)) {
                    time++;
            }
        }

        System.out.println(graph[x-1][y-1]);

        /*
        경쟁적 전염
        N x N 시험관
        특정한 위치에는 바이러스가 존재할 가능성 1 ~ K번까지 K가지의 바이러스
        1초마다 상하좌우로 증식
        매초 번호가 낮은 종류의 바이러스부터 먼저 증식
        가려는 칸에 다른 바이러스 있다면 갈 수 없음

        S초 지난 후 특정 좌표 (X, Y)에 위치하는 바이러스 출력
        */


    } // end main method
}