[JAVA] 백준 2636 : 치즈

문제

2636번: 치즈

 

해결 방법

조금 생각할 것이 있는 구현 문제이다.

 

필자는 다음과 같은 순서로 문제를 해결했는데,

 

1.

배열의 (0, 0) 부터 빈 공간인 0을 탐색, 만약 0의 상하좌우에 치즈 즉, 1이 있다면 Queue에 넣음.

모든 공간을 다 탐색하면 Queue에 넣어진 치즈들이 한 시간 후 녹을 치즈들이 됨.

재귀를 통해서 모든 치즈들이 없어질 때까지 탐색을 계속함.

 

2.

Queue에서 치즈를 꺼내면서 빈공간으로 바꿔주면서 상하좌우에 있는 치즈를 찾음.

만약 치즈가 있다면 다음 녹을 치즈이므로 새로운 pre 라는 이름의 Queue에 저장.

탐색 도중에 방문하지 않은 빈 공간 즉, 치즈 안에 있던 빈 공간을 찾게되면 빈 공간을 탐색하는 Queue를 새로 돌림.

해당 빈 공간 상하좌우에 있는 치즈들도 다음에 녹을 치즈이므로 pre 라는 이름에 Queue에 저장해줌.

 

3.

탐색이 종료된 후에 다음에 녹아야할 치즈가 들어있는 pre 라는 이름의 Queue가 비어있지않다면 다시 재귀를 돌려 추가 탐색을 하고 비었다면 더 이상 녹아야할 치즈가 없는 것이므로 종료함.

 

시간은 변수로 체크하고 현재 Queue의 크기를 사용해서 녹기 전 치즈의 개수를 저장.

 

자세한 내용은 코드에 주석을 달아두었다.

 

코드

package baekJoonSolo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_2636 {
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	static boolean[][] visited;
	static int[][] map;
	static int r, c;
	static int day = 0;
	static int preCnt = 0;
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		map = new int[r][c];
		for (int i = 0; i < r; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < c; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		visited = new boolean[r][c];
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(0, 0));
		visited[0][0] = true;
		
		Queue<Node> preC = new LinkedList<>();
		
		// 첫 번째 녹아야할 치즈 찾기
		while (!q.isEmpty()) {
			Node node = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nr = node.r + dr[i];
				int nc = node.c + dc[i];
				
				// 범위를 벗어나거나 방문한 곳이면 넘김
				if (nr < 0 || nc < 0 || nr >= r || nc >= c || visited[nr][nc]) continue;
				
				if (map[nr][nc] == 0) {
					q.offer(new Node(nr, nc));
					visited[nr][nc] = true;
				}
				
				if (map[nr][nc] == 1) {
					preC.offer(new Node(nr, nc));
					map[nr][nc] = 0;
					visited[nr][nc] = true;
				}
			}
		}
		go(preC);
		
		System.out.println(day);
		System.out.println(preCnt);	
	}
	static void go(Queue<Node> cur) {
		day++;					// 시간 증가
		preCnt = cur.size();	// 녹기 전 치즈 갯수 저장
		
		// 앞으로 녹아야할 치즈 보관
		Queue<Node> pre = new LinkedList<>();
		
		while (!cur.isEmpty()) {
			Node node = cur.poll();
			for (int i = 0; i < 4; i++) {
				int nr = node.r + dr[i];
				int nc = node.c + dc[i];
				
				// 범위를 벗어나거나 방문한 곳이면 넘김
				if (nr < 0 || nc < 0 || nr >= r || nc >= c || visited[nr][nc]) continue;
				
				// 치즈 안에 있는 0 주위의 1은 다음 차례에 녹아야한다.
				if (map[nr][nc] == 0) {
					Queue<Node> air = new LinkedList<>();
					visited[nr][nc] = true;
					air.offer(new Node(nr, nc));
					
					while (!air.isEmpty()) {
						Node node2 = air.poll();
						for (int j = 0; j < 4; j++) {
							int nnr = node2.r + dr[j];
							int nnc = node2.c + dc[j];
							
							// 범위를 벗어나거나 방문한 곳이면 넘김
							if (nnr < 0 || nnc < 0 || nnr >= r || nnc >= c || visited[nnr][nnc]) continue;
							
							// 공기 구멍을 탐사
							if (map[nnr][nnc] == 0) {
								air.offer(new Node(nnr, nnc));
								visited[nnr][nnc] = true;
							}
							
							// 탐사한 공기구멍 근처 치즈는 다음 차례에 녹아야함
							if (map[nnr][nnc] == 1) {
								pre.offer(new Node(nnr, nnc));
								visited[nnr][nnc] = true;
								map[nnr][nnc] = 0;
							}
						}
					}
				}
				
				if (map[nr][nc] == 1) {
					pre.offer(new Node(nr, nc));
					map[nr][nc] = 0;
					visited[nr][nc] = true;
				}
			}
		}
		
		// 아직 녹아야 할 치즈가 남아있다면
		if(pre.size() != 0) go(pre);
		else return;
	}
	
	static class Node {
		int r;
		int c;
		
		Node (int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
}