문제 정리

---

N x N의 시험관에 1~K의 바이러스가 있을 때 숫자가 작은 바이러스가 먼저 퍼진다. 그리고 원래 바이러스가 있는 칸에 다른 바이러스가 들어갈 수 없다
S초 후 내가 원하는 칸에 무슨 바이러스가 있는지 알아보는 문제다

입력

N K       //N=맵 크기, K=바이러스 종류 (1,2,...K)
시험관 정보
S X Y      //S=몇 초 후, X=row, Y=col
          //시험관의 각 칸은 1부터 시작한다

출력

S초 후 X,Y 칸에 있는 바이러스 번호
아무런 바이러스도 없을 경우 0

idea 정리

---

우선순위가 필요해서 priority queue를 떠올릴 수 있지만
pq를 쓰게 될 경우는 같은 번호의 바이러스만 퍼지는 결과가 나올 수 있다
1번 바이러스가 퍼지고 난 후 2번 바이러스가 아닌 1 바이러스가 또 퍼지기 때문이다

일반 bfs로 구현할 경우 처음 퍼지는 순서만 오름차순으로 퍼지면 새로 q에 쌓이는 바이러스들은 자동으로 오름차순로 쌓인다.
따라서,
bfs를 돌기 전에만 바이러스를 오름차순으로 정리해 주면 된다.

알고리즘 구성

---

1. list에 바이러스를 넣어준다
2. list의 바이러스를 번호를 기준으로 정렬
3. list의 바이러스를 q에 넣고 bfs
4. S초 만큼 bfs를 돈다

구현

---

//경쟁적 전염
public class Main {
	static class Virus implements Comparable<Virus>{
		int r, c, num;
		
		public Virus(int r, int c, int num) {
			super();
			this.r = r;
			this.c = c;
			this.num = num;
		}

		@Override
		public int compareTo(Virus o) {
			return this.num - o.num;
		}
	}
	static int N, K, S, X, Y;
	static int[][] map;
	static Queue<Virus> q;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		q = new LinkedList<>();
		
		List<Virus> virusList = new ArrayList<>();
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				int value = Integer.parseInt(st.nextToken());
				map[i][j] = value;
				
				if(value > 0) {
					virusList.add(new Virus(i, j, value));
				}
			}
		}
		
		Collections.sort(virusList);
		for(int i=0, size=virusList.size(); i<size; i++) {
			q.add(virusList.get(i));
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		S = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken())-1;
		Y = Integer.parseInt(st.nextToken())-1;
		
		bfs();
		
		bw.write(map[X][Y] + "");
		bw.flush();
		bw.close();
		br.close();
	}
	
	static void bfs() {
		int time = 0;
		int[] dr = {-1, 1, 0, 0};		//상 하 좌 우
		int[] dc = {0, 0, -1, 1};
		
		while(!q.isEmpty()) {
			if(time==S) return;
			
			for(int i=0,size=q.size(); i<size; i++) {
				Virus now = q.poll();
				
				for(int j=0; j<4; j++) {
					int nr = now.r + dr[j];
					int nc = now.c + dc[j];
					
					if(0<=nr && nr<N && 0<=nc && nc<N && map[nr][nc]==0) {
						map[nr][nc] = now.num;
						q.offer(new Virus(nr, nc, now.num));
					}
				}
			}
			time++;
		}
	}
}

결과

---