[Baekjoon] 백준 18405 전염 (G5^ / BFS, PQ) - Java

링크

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

18405번: 경쟁적 전염

 

 

 

 

문제 해석

N*N 시험관
특정 위치에는 바이러스가 존재 가능
모든 바이러스는 1~K 중 하나

모든 바이러스는 1초마다 상하좌우로 증식
낮은 종류의 바이러스가 먼저 증식
특정 칸에 이미 바이러스가 존재하면 다른 바이러스가 들어갈 수 없음
S초 후 (X, Y)에 존재하는 바이러스 종류를 출력
처음 시작은 0초

 

 

입력
첫 번째 줄 : N, K
  N : 가로 세로 시험관 크기
  K : 바이러스 종류
N개의 줄 : 시험관의 바이러스 위치
N + 2번째 줄 : S, X, Y
  S : 시작 후 지난 초
  X, Y : 찾을 바이러스 위치 


출력
(X, Y)에 위치한 바이러스 번호 출력
단 해당 위치에 바이러스가 존재하지 않는다면 0을 출력

 

 

 

풀이 & 코드 해석

얼핏보면 간단한 BFS 문제라고도 볼 수 있습니다.

 

문제는 각 바이러스가 우선순위를 가진다는 점인데, 이를 해결하기 위해서 PriorityQueue를 사용했습니다.

 

 

PQ를 통해서 매번 데이터를 집어넣을 때마다 우선순위를 확인하고 우선순위가 높은 Point부터 차례대로 지도에 그려줍니다.

 

 

지도에 그릴 Point가 최초로 S를 넘어가면 (X, Y) 좌표를 출력하도록 하였습니다. 

 

(X, Y)는 (0, 0) 부터가 아닌 (1, 1)부터 시작이므로, 각각 -1을 해줘야 합니다.

 

 

 

코드

package test;

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

public class 경쟁적전염 {

	static int[][] map;
	static int S;
	static int X;
	static int Y;
	static int answer;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		answer = 0;
		
		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());
			}
		}
		
		// print();
		
		st = new StringTokenizer(br.readLine());
		S = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken()) - 1;
		Y = Integer.parseInt(st.nextToken()) - 1;
		
		bfs();
		
		// pq가 모두 호출되기 전에 S초 만큼 지나서 끝난 상태
		if (answer != 0) {
			System.out.println(answer);
			return;
		}
		
		// S초보다 빨리 pq가 끝난 상태
		System.out.println(map[X][Y]);
		
	}
	
	static class Point implements Comparable<Point> {
		int r;
		int c;
		int virus;
		int level;
		
		Point (int r, int c, int virus, int level) {
			this.r = r;
			this.c = c;
			this.virus = virus;
			this.level = level;
		}

		@Override
		public int compareTo(Point other) {
			int compareLevel = Integer.compare(this.level, other.level);
			
			if (compareLevel == 0) {				
				return Integer.compare(this.virus, other.virus); // level 기준 오름차순
			}
			return compareLevel;
		}
	}
	
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = {0, 1, 0, -1};
	
	static void bfs() {
		PriorityQueue<Point> pq = new PriorityQueue<>();
		
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if (map[i][j] != 0) {
					pq.offer(new Point(i, j, map[i][j], 0));
				}
			}
		}
		
		while(!pq.isEmpty()) {
			Point p = pq.poll();
			
			if (p.level == S) {
				answer = map[X][Y];
				return;
			}
			
			for (int d = 0; d < dr.length; d++) {
				int nr = p.r + dr[d];
				int nc = p.c + dc[d];
				
				if (nr >= 0 && nr < map.length && nc >= 0 && nc < map[0].length 
						&& map[nr][nc] == 0) {
					map[nr][nc] = p.virus;
					pq.offer(new Point(nr, nc, p.virus, p.level + 1));
				}
			}
			
		}
	}

	static void print() {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

 

 

 

 

발생한 문제 & 해결 방안

오랜만에 해서 PriorityQueue를 까먹었다.
어제는 Map도 가물가물하던데.. 큰일이다..

 

pq로 했다 -> 정답이 1또는 0만 나온다 -> pq는 새로 넣으면 1만 계속 반복되네??
처음에 비교를 virus로만 했는데 생각해보니 당연하게도 virus 기준으로 넣을 때마다 순서가 정해지니 1만 나올 수 밖에 없다..
-> 처음에는 level로, 그다음 virus로 비교하기

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java