[백준 / BOJ] 18405번 : 경쟁적 전염 - JAVA

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

18405번: 경쟁적 전염

Queue 배열

"번호가 낮은 바이러스부터 증식한다" 라는 조건이 있기 때문에 Queue를 여러 개 사용하기로 했다. 큐 배열을 만들어서 각 번호를 인덱스로 위치를 저장하는 것이다. 그리고 매초마다 반복해야 하기 때문에 time이라는 변수를 두고, 큐에도 시간을 넣어 저장하도록 했다.

 

전체 코드

 

// 시간: 272ms
// 메모리 : 19728KB
public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		Queue<int[]>[] que = new LinkedList[K + 1];
		
		for (int i = 0; i <= K; i++) {
			que[i] = new LinkedList<>();
		}
		
		int[][] map = new int[N][N];
		
		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) {
					que[map[i][j]].offer(new int[] {i, j, 0});
				}
			}
		}
		
		st = new StringTokenizer(br.readLine());
		
		int S = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken()) - 1;
		int Y = Integer.parseInt(st.nextToken()) - 1;
		
		
		int[] dr = {-1,0,1,0};
		int[] dc = {0,-1,0,1};
		int time = 0;
		while(time < S) {
			for (int i = 1; i <= K; i++) {
				while(!que[i].isEmpty()) {
					if(que[i].peek()[2] == time) {
						int[] cur = que[i].poll();
						for (int d = 0; d < 4; d++) {
							int nr = cur[0] + dr[d];
							int nc = cur[1] + dc[d];
							
							if(nr >= N || nc >= N || nr < 0 || nc < 0) continue;
							if(map[nr][nc] > 0) continue;
							map[nr][nc] = i;
							que[i].offer(new int[] {nr, nc, cur[2] + 1});
						}
					} else break;
				}
			}
			time++;
		}
		System.out.println(map[X][Y]);
	}

}