[BOJ 18405] 경쟁적 전염

문제

• BOJ 18405
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

1. 입력값을 받아 map배열에 좌표값을 표시하고, 바이러스인 경우 큐에 모두 넣어준다. 큐에서 꺼냈을 때 번호가 작은 순으로 나오기 위해 우선순위큐를 사용해주었고, Comparable을 사용해서 번호 기준으로 오름차순 정렬되도록 해주었다.
2. 주어진 시간만큼 큐에 있는 바이러스를 모두 꺼내서 퍼뜨리면 되는데, 다음 칸이 빈칸이면 현재 바이러스 번호로 전염시키기 위해 맵에 표시해준다. 그리고 바로 큐 q에 넣는것이 아니라 새로 만든 큐 qq에 넣어서 따로 관리해줘야한다. 만약 q에 넣게되면 만약 방금 넣은 값의 번호가 기존에 큐에 있던 번호들보다 작은 경우, poll()했을 때 방금 넣은 번호가 나오게 되는 문제가 발생한다.

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

//경쟁적 전염
class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, K; // 크기, 바이러스 최대 번호
	static int S, X, Y; // 시간, 출력 좌표
	static int[][] map;
	static PriorityQueue<Point> q; // 바이러스 관리
	static PriorityQueue<Point> pq; // 탐색하면서 다음 바이러스 관리
	static int[][] dArr = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // 상하좌우

	static class Point implements Comparable<Point> {
		int num, x, y;

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

		@Override
		public int compareTo(Point o) { //번호가 작은 순으로 정렬
			return this.num - o.num;
		}
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		q = new PriorityQueue<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] != 0) q.add(new Point(map[i][j], i, j));
			}
		}
		st = new StringTokenizer(br.readLine());
		S = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken())-1;
		Y = Integer.parseInt(st.nextToken())-1;
		
	    while(S-- >0 && !q.isEmpty() && map[X][Y] == 0) { //주어진 시간만큼 탐색
			int size = q.size();
			pq = new PriorityQueue<>();
			while(size-- > 0) {
				Point now = q.poll();
				
				for(int d=0; d<4; d++) {
					int nx = now.x + dArr[d][0];
					int ny = now.y + dArr[d][1];
					
					if(nx>=0 && nx<N && ny>=0 && ny<N && map[nx][ny] == 0) { //비어있으면
						map[nx][ny] = now.num; //바이러스 퍼뜨리기
						pq.add(new Point(map[nx][ny], nx, ny)); //pq가 아니라 q에 계속 넣으면 우선순위큐에서 꺼내줄 때 영향을 줌
					}
				}
			}
			q = pq;
		}
		
		//X,Y에 있는 바이러스 종류 출력
		System.out.println(map[X][Y]); //배열의 크기가 0부터 시작하므로 하나 빼줌
	}
}