[BOJ] 경쟁적 전염 for Java - PriorityQueue를 적용한 풀이

문제 바로가기

18405번: 경쟁적 전염

 

문제풀이

시험관에 존재하는 바이러스는 1초마다 번호순으로 증식되기 때문에 BFS를 적용하도록 한다. 
PriorityQueue를 사용하여 시간/번호순으로 정렬이 가능하도록 Virus 클래스에 Comparable 인터페이스를 적용한다.

 

구현

0. Virus 클래스에 Comparable을 적용하여, 시간순 -> 번호순으로 큐가 정렬되도록 함
1. 바이러스가 존재하면 PriorityQueue에 offer
2-1. X, Y 좌표에 바이러스 존재하면 return 
2-2. S초에 도달했다면 return 
3. 상하좌우를 탐색하며 바이러스가 없는 곳에 바이러스 증식시키고, pq에 offer
4. 결과값 출력 

 

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int N, K, S, X, Y, map[][];
	static StringTokenizer st;
	static int dir[][] = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
	static PriorityQueue<Virus> pq = new PriorityQueue<Virus>();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N][N];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < N; m++) {
				map[n][m] = Integer.parseInt(st.nextToken());
				if (map[n][m] != 0)
					pq.add(new Virus(n, m, map[n][m], 0));
			}
		}

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

		virus();

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

	public static void virus() {

		while (!pq.isEmpty()) {
			Virus cur = pq.poll();
			
			if(map[X-1][Y-1] != 0)
				return;
			
			if(cur.time == S)
				return;
			
			for (int d = 0; d < 4; d++) {
				int nx = cur.x + dir[d][0];
				int ny = cur.y + dir[d][1];

				if (nx >= 0 && ny >= 0 && nx < N && ny < N && map[nx][ny] == 0) {
					map[nx][ny] = cur.num;
					pq.offer(new Virus(nx, ny, cur.num, cur.time + 1));
				}
			}
		}
	}

	private static class Virus implements Comparable<Virus> {

		int x;
		int y;
		int num;
		int time;

		public Virus() {
			super();
		}

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

		public int getX() {
			return x;
		}

		public int getY() {
			return y;
		}

		public int getNum() {
			return num;
		}

		public int getTime() {
			return time;
		}

		@Override
		public int compareTo(Virus o) {
			return Comparator.comparing(Virus::getTime)
					.thenComparing(Virus::getNum)
					.compare(this, o);
		}
	}
}

 

마치며

2개 이상의 필드로 객체를 비교하기 위해 Comparable의 compareTo를 구현하면서 comparing 메서드를 사용해보았습니다.

Comparator.comparing(Virus::getTime)
                    .thenComparing(Virus::getNum)
                    .compare(this, o);

객체 비교는 아직 공부할 부분이 너무 많은 것 같습니다. 기회가 된다면 객체 비교부분을 학습하고 포스팅하고 싶습니다.