[백준/자바] 2636번: 치즈

문제

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

풀이

• N*M 크기의 판
• 치즈의 겉면은 공기에 닿으면 녹게 됨
  • 치즈 안에 있는 구멍 속에는 공기가 없으므로 녹지 않음!
• 치즈가 모두 녹아내리는 데 걸리는 시간, 녹기 한 시간 전에 남아있는 치즈 조각의 개수 출력

BFS를 사용하여 한 겹씩 벗겨내면 됩니다.

저는 처음에 너무 어렵게 접근하다가 코드를 짜면서 알아냈습니다..

		// 판 초기화
		map = new int[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) cheese++; // 치즈 조각
			}
		}

맵을 초기화할 때, 치즈의 개수를 먼저 세줍니다.

		cnt = 0; time = 0;
		while (cheese > 0) { // 치즈가 0이 될 때까지 진행
			cnt = cheese; // 현재 치즈 조각의 개수
			time++; // 시간 증가
			bfs(); // 치즈 녹이기 시작
		}

cheese의 개수가 0이 될 때까지 반복합니다.

	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {0, 0}); // (0, 0)부터 시작
		boolean[][] visited = new boolean[n][m];
		visited[0][0] = true; // 방문 처리
		
		while (!queue.isEmpty()) {
			int[] p = queue.poll();
			int r = p[0], c = p[1];
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				// 범위 밖 || 방문 했다면 pass
				if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc]) continue;
				
				visited[nr][nc] = true; // 방문 처리

				if (map[nr][nc] == 0) { // 공기일 경우 그냥 퍼져나감
					queue.offer(new int[] {nr, nc});
				} else { // 치즈일 경우
					cheese--; // 치즈 개수 - 1
					map[nr][nc] = 0; // 치즈 녹이기
				}
			}
		}
	}

(0, 0)부터 시작하여 모든 좌표를 탐색합니다.

• 만약 공기를 만났을 경우 방문 처리만 하고 다음 좌표를 탐색합니다.
• 치즈를 만났을 경우 치즈의 개수를 줄이고, 해당 좌표를 공기로 바꿔 줍니다.
  여기서 주의하실 점은 바로 이 치즈의 좌표를 큐에 넣지 않는다는 겁니다!!

코드

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

public class Main {
	static int n, m;
	static int cheese, cnt, time;
	static int[][] map;
	
	static final int[] dr = {-1, 1, 0, 0};
	static final int[] dc = {0, 0, -1, 1};
	
	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {0, 0}); // (0, 0)부터 시작
		boolean[][] visited = new boolean[n][m];
		visited[0][0] = true; // 방문 처리
		
		while (!queue.isEmpty()) {
			int[] p = queue.poll();
			int r = p[0], c = p[1];
			
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				
				// 범위 밖 || 방문 했다면 pass
				if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc]) continue;
				
				visited[nr][nc] = true; // 방문 처리

				if (map[nr][nc] == 0) { // 공기일 경우 그냥 퍼져나감
					queue.offer(new int[] {nr, nc});
				} else { // 치즈일 경우
					cheese--; // 치즈 개수 - 1
					map[nr][nc] = 0; // 치즈 녹이기
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 행
		m = Integer.parseInt(st.nextToken()); // 열
		
		// 판 초기화
		map = new int[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) cheese++; // 치즈 조각
			}
		}
		
		cnt = 0; time = 0;
		while (cheese > 0) { // 치즈가 0이 될 때까지 진행
//			view();
			cnt = cheese; // 현재 치즈 조각의 개수
			time++; // 시간 증가
			bfs(); // 치즈 녹이기 시작
		}
		
		System.out.println(time + "\n" + cnt);
	}
	
	private static void view() {
		System.out.println();
		for (int[] line : map) {
			for (int v : line) System.out.print(v + " ");
			System.out.println();
		}
	}
}