[Java] 백준 18405 경쟁적 전염

백준 18405 경쟁적 전염

풀이

Virus 객체를 만들어 num으로 정렬할 수 있도록 Comparable을 implements하여 compareTo를 override하였습니다.

입력을 받으면서 0이 아닌 숫자들은 PriorityQueue에 담았습니다.

주어진 S만큼 for문을 돌며 현재 pq에 있는 Virus를 퍼뜨립니다. 정렬이 되어있으니 자동으로 내림차순으로 Virus를 퍼뜨립니다.
이 때, bfs를 돌며 현재 pq에 Virus를 추가하면 정상 동작하지 않습니다. 예를 들어 1초에 우린 입력에 주어진 1, 2, 3 바이러스가 퍼지길 원하지만 저렇게 처리하면 PriorityQueue이기 때문에 1, 1, 1이 처리될 것입니다.

따라서 다음 초에 퍼져야 할 Virus는 별도의 nextPq라는 PriorityQueue에 add하는 방식으로 진행하였습니다.

코드

import java.util.*;
import java.io.*;
public class B18405_CompetitiveContagion {
    static class Virus implements Comparable<Virus> {
        int x;
        int y;
        int num;

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

        @Override
        public int compareTo(Virus o) {
            return this.num - o.num;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str[] = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);

        int map[][] = new int[N][K];
        PriorityQueue<Virus> pq = new PriorityQueue<>();

        for(int i = 0;i < N;i++) {
            str = br.readLine().split(" ");
            for(int j = 0;j < N;j++) {
                map[i][j] = Integer.parseInt(str[j]);
                if(map[i][j] != 0) pq.add(new Virus(i, j, map[i][j]));
            }
        }

        str = br.readLine().split(" ");
        int S = Integer.parseInt(str[0]);
        int X = Integer.parseInt(str[1]);
        int Y = Integer.parseInt(str[2]);

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

        for(int i = 0;i < S;i++) {
            int size = pq.size();
            PriorityQueue<Virus> nextPq = new PriorityQueue<>();

            for(int j = 0;j < size;j++) {
                Virus temp = pq.poll();

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

                    if(nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] != 0) continue;

                    map[nx][ny] = temp.num;
                    nextPq.add(new Virus(nx, ny, temp.num));
                }
            }

            pq = nextPq;
        }

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

후기

• 뭔가...덜 효율적인 느낌... 더 효율적으로 구현할 방법을 찾아보자!