[BJ] 18405 경쟁적 전염 Java

백준 18405 경쟁적 전염

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

18405번: 경쟁적 전염

아이디어

• 백준 7576 토마토  문제와 비슷하게 큐에 먼저 필요한 개체를 넣어야함
• 바이러스의 종류가 1~K번이 있는데, 작은 바이러스가 먼저 퍼진다 --> 토마토 문제와 비슷하게 익은 토마토를 먼저
• 즉, 낮은 번호의 바이러스를 큐에 넣는다. 바이러스의 순서를 정하기 위해서는 바이러스 객체에 x,y 뿐만 아니라 index값과 시간 저장한다.
• 입력받으면서 0이 아닌경우, 즉 바이러스가 있다 --> 바이러스를 추가함
• 바이러스를 정렬하고 큐에 넣어줌 
• 상하좌우에 대해서 0인 경우 바이러스가 퍼질 수 있으니 해당 칸은 현재 바이러스의 인덱스로 업데이트하고
• 새로운 바이러스를 큐에 넣을때는 시간 + 1인 값을 넣는다
• 시간 == s 가 되면 그래프에 바이러스 정보가 있음. 배열 인덱스를 0부터 시작했기 때문에 [x-1][y-1] 좌표를 보면 됨

코드

import java.util.*;

class Main {
    // 바이러스 클래스
    static class Virus implements Comparable<Virus> {
        int x,y,index,time;
        public Virus(int x, int y, int index, int time) {
            this.x = x;
            this.y = y;
            this.index = index;
            this.time = time;
        }
        @Override 
        // 번호가 작은 바이러스부터 퍼짐 그래서 다시 재정렬
        public int compareTo(Virus other) {
            return this.index - other.index;
        }
    }
    
    static Queue<Virus> q = new LinkedList<>();
    static int n, k, s, x, y;
    static int[][] graph;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        
        graph = new int[n+1][n+1];
        ArrayList<Virus> virus = new ArrayList<>();
        
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                graph[i][j] = sc.nextInt();
                // 바이러스가 없는 곳은 0이고, 바이러스가 있다면 해당 바이러스 정보 추가
                if (graph[i][j] != 0) virus.add(new Virus(i,j,graph[i][j], 0));
            }
        }
        
        s = sc.nextInt(); // 초
        x = sc.nextInt(); // (x,y) 에 있는 바이러스 번호
        y = sc.nextInt();
        
        Collections.sort(virus); // 작은 바이러스부터 퍼져야함 --> 즉 먼저 탐색
        for (Virus v : virus) q.offer(v);
        
        BFS();
        
        System.out.println(graph[x-1][y-1]);
    }
    
    public static void BFS() {
        while (!q.isEmpty()) {
            Virus v = q.poll();
            // 입력받은 s와 시간이 같으면 멈춤
            if (v.time == s) return;
            
            // 4방향에 대해서 바이러스 확인
            for (int i=0; i<4; i++) {
                int nx = v.x + dx[i];
                int ny = v.y + dy[i];
                
                // 0인 경우 바이러스가 퍼질 수 있음. 시작하고 있는 바이러스 인덱스로 업데이트하고
                // 시간을 +1 해서 저장
                if (nx>=0 && ny>=0 && nx<n && ny<n) {
                    if (graph[nx][ny] == 0) {
                        graph[nx][ny] = v.index;
                        q.offer(new Virus(nx, ny, v.index, v.time+1));
                    }
                }
            }
        }
    }
}