[BOJ] 백준 [18405] 경쟁적 전염 JAVA

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

18405번: 경쟁적 전염

📝 문제

 

 

📝 풀이

S 초 뒤에 해당 위치 (X,Y) 의 바이러스 상태를 return 하는 문제이다.

바이러스가 퍼지는 조건은 번호 순 대로 차례대로 퍼진다
따라서 순위를 보장해 주는 우선순위큐에 주어진 map 의 좌표를 다음과 같은 순서로 넣는다
1. 시간순 
2. 번호순

BFS를 수행하면서 탐색 할 위치에 바이러스가 없다면 map 의 값을 갱신
만약 종결조건인 S 시간에 도달하였을 경우 종료 

 

import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;

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


public class Main {

    static int[][] map;
    static int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
    static int n, k;
    static Queue<Virus> pq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        n = input[0];
        k = input[1];
        map = new int[n + 1][n + 1];

        pq = new PriorityQueue<>((v1, v2) ->
                v1.time == v2.time ? v1.type - v2.type : v1.time - v2.time); // 1.시간순 2.번호순 정렬

        for (int i = 1; i <= n; i++) {
            map[i] = stream(("0 " + br.readLine()).split(" "))
                    .mapToInt(Integer::parseInt).toArray();

            for (int j = 1; j <= n; j++) {
                if (map[i][j] != 0)
                    pq.add(new Virus(j, i, map[i][j], 0));
            }
        }
        int[] endCondition = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        //end input

        System.out.println(bfs(endCondition));
    }

    private static int bfs(int[] end) {

        while (!pq.isEmpty()) {

            Virus cur = pq.poll();

            if (cur.time >= end[0])  // 종견조건 : 주어진 시간 S 에 다다랐을 때
                break;

            for (int i = 0; i < dx.length; i++) {

                int nextX = cur.x + dx[i];
                int nextY = cur.y + dy[i];

                if (!isRange(nextX, nextY) || map[nextY][nextX] != 0) // 이미 그 위치에 바이러스가 존재하면 안됨
                    continue;

                map[nextY][nextX] = cur.type; // 바이러스 생성
                pq.add(new Virus(nextX, nextY, cur.type, cur.time + 1));
            }
        }
        return map[end[1]][end[2]];
    }

    static boolean isRange(int x, int y) {
        return x > 0 && y > 0 && x <= n && y <= n;
    }

    static class Virus {
        int x, y, type, time;

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