[백준/Java] 18405번 : 경쟁적 전염

문제

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

 

3055번 탈출(https://www.acmicpc.net/problem/3055) 문제와 비슷한 문제가 시험에 나왔다.

탈출 문제를 완전히 이해하기 전에 시험을 쳐서 그런지 이 문제 또한 못 풀었다.

오늘 풀이하고 집 가야지..

풀이

문제에서 고려할 점은 

1. 여러 개의 바이러스가
2. 1초 마다
3. 번호가 작은 순서대로 확산된다는 것이다.

k초에 수행되는 것 :

• 'k-1초에 큐에 넣었던 좌표'의 모든 인접 좌표에 대해 bfs 수행
• 단, 바이러스 크기가 작은 좌표부터 차례로 수행해야 함

바이러스 크기가 작은 것부터 확산하는 아이디어 :

• 우선순위 큐를 사용해서 좌표를 바이러스 크기 순서대로 꺼내기 :
  -> 잘못된 방식이다. 바이러스 1을 bfs로 퍼뜨리면서 바이러스 1의 인접 좌표를 바로 우선순위 큐에 넣게 되는데,
  이 때 다음 초에 bfs가 수행되어야 할 바이러스 1의 좌표를 현재 턴에서 계속 수행하게 된다. 
• 맨 처음 큐에 바이러스의 좌표를 넣을 때 바이러스 크기 순서대로 삽입하기 :
  -> 처음에 큐에 바이러스 좌표를 넣을 때 바이러스 크기 순서대로 정렬해서 넣으면 우선순위 큐 없이도 해결 가능하다.
  큐에 들어가는 원소 하나는 바이러스의 좌표, 바이러스의 크기, 몇 초에 bfs 수행될 좌표인지의 정보를 포함하면 된다.
  예) 바이러스가 3개일 때 큐에 바이러스1, 2, 3 순서로 좌표 삽입, 각 좌표가 1초에 수행될 좌표임을 표시 
       -> 이미 큐에 바이러스가 오름차순으로 들어가있으므로 순서 조건을 만족하면서 확산이 수행됨
       -> 1초에는 1초라고 표시되어있는 좌표까지만 bfs 수행하고 끝내기
       -> bfs 수행하면서 만난 인접 좌표들을 큐에 넣을 때는 현재 초+1로 표시하기
• 트리맵을 이용한 방식(자바) 
  -> 아직 이해 못 했다. 담에 써야지

코드 설계

1. 입력 받기 
   1. 입력 받으면서 바이러스를 발견하면 virus 리스트에 좌표와 바이러스 번호를 저장
2. virus 리스트를 바이러스 번호 기준 오름차순으로 정렬
3. 큐에 정렬된 바이러스들을 차례로 넣기
   1. 큐에 삽입될 바이러스 객체는 (바이러스 좌표, 바이러스 번호, 확산이 수행될 시간) 정보를 포함한다
4. 다음 과정을 1초부터 S초까지 총 S번 수행
   1. 큐에서 시간이 k초인 바이러스를 꺼내 상하좌우로 확산시킴
   2. 확산된 곳에 해당 바이러스 번호를 저장
   3. 이미 바이러스가 차있는 곳이면 확산시키지 않음 (덮어쓰기 x)
   4. 바이러스를 새로 확산시킨 좌표를 큐에 넣을 때 시간을 1 증가시켜서 넣기
5. 좌표 (x, y)에 저장된 바이러스 번호를 출력

코드

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

public class Main {
    static int N, K, S, X, Y;
    static int[][] arr;
    static Queue<Node> q = new LinkedList<>();
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int[][] time;
    static List<Node> virus = new ArrayList<>();

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

        arr = new int[N][N];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]>0){
                    virus.add(new Node(i, j, arr[i][j], 1));
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        Collections.sort(virus);

        for(Node n: virus){
            q.offer(n);
        }

        for(int time=1; time<=S; time++)
            bfs(time);

        System.out.println(arr[X-1][Y-1]);
    }

    static void bfs(int time){
        //time초에 수행되어야 할 바이러스들만 bfs

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

            if(now.t != time) //time초가 아니면 탐색 중단
                break;

            for(int i=0; i<4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if(nx<0 || nx>=N || ny<0 || ny>=N)
                    continue;

                if(arr[nx][ny] != 0) //이미 바이러스가 저장된 곳이면 확산 x
                    continue;

                arr[nx][ny] = now.n; //확산된 좌표에 바이러스 번호 저장하기
                q.offer(new Node(nx, ny, now.n, now.t+1));
            }
        }
    }

}

class Node implements Comparable<Node>{
    int x, y, n, t; //바이러스 좌표, 바이러스 번호, 확산이 수행될 시간
    Node(int x, int y, int n, int t){
        this.x = x;
        this.y = y;
        this.n = n;
        this.t = t;
    }

    @Override
    public int compareTo(Node o) {
        return this.n-o.n;
    }
}