치즈


백준 2636: 치즈

문제보기
Alt text

풀이

BFS를 이용
녹을 치즈를 저장해 놓았다가 탐색이 끝난 후 한꺼번에 치즈를 녹이는 것이 중요
처음 1시간 안에 치즈가 다 녹을 수 있음을 주의
->그래서 처음 입력 받을 때부터 치즈조각 개수를 세어줌

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static class Node {
		int r, c;
		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt(); // 판의 세로의 길이(행)
		int w = sc.nextInt(); // 판의 가로의 길이(열)
		int[][] map = new int[h][w];
		int cheese = 0;	//치즈조각의 개수
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j]==1)
					cheese++;
			}
		}
		int time = 0;
		Queue<Node> queue = new LinkedList<>();
		boolean flag = true;
		
		while (flag) {
			time++;
			boolean visited[][] = new boolean[h][w];

			queue.add(new Node(0, 0));
			visited[0][0] = true;

			while (!queue.isEmpty()) {
				Node node = queue.poll();
				for (int d = 0; d < 4; d++) {
					int nr = node.r + dr[d];
					int nc = node.c + dc[d];

					if (nr >= 0 && nc >= 0 && nr < h && nc < w && !visited[nr][nc]) {
						if (map[nr][nc] == 0) {
							queue.add(new Node(nr, nc));
							visited[nr][nc] = true;
						} else if (map[nr][nc] == 1) {
							map[nr][nc] = 2; // 녹을 자리이면 그 곳을 2로 바꿔준다
						}
					}
				}
			}

			// 치즈 녹이기
			int cnt = 0;	// 현재 치즈조각 개수
			boolean check = false;	//다음에 녹을 치즈가 남아있는지 확인하기 위해
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (map[i][j] == 2) {
						map[i][j] = 0;
					} else if (map[i][j] == 1) {
						cnt++;
						check = true;
					}
				}
			}
			
			if(check)	//녹을 치즈가 있으면 현재까지의 치즈조각 개수 저장
				cheese = cnt;			
			
			if(!check)	//더이상 녹을 치즈가 없으면 끝내기
				flag = false;
		}
		System.out.println(time);
		System.out.println(cheese);
	}
}