[백준] 2636번 치즈

공기에 닿은 치즈는 녹아 없어지며, 치즈가 모두 녹을 때까지의 시간과 마지막으로 남아있던 치즈조각들을 출력한다.

BFS를 활용하면 쉽게 풀리는 문제로, 꼬아서 생각해서 시간이 오래 걸렸던 문제 :(

[문제] 백준 2636번 : 치즈

풀이 방법

1. Input과정에서 치즈의 개수를 저장한다.

2. cheeze의 개수가 0이 될때 까지 bfs를 반복, cnt를 저장하고 time을 증가시킨다.

   2-1. bfs는 (0, 0)에서 시작

   2-2. 공기를 만나면 Queue에 삽입,
   

           치즈를 만나면 0으로 변경하고 치즈의 개수를 줄인다.

   2-3. 치즈와 공기 상관없이 방문처리 필수!

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

public class Main {
	public static int N, M, cheeze, cnt, time;
	public static int[][] map;
	public static boolean[][] v;
	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		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)
					cheeze++;
			}
		}
		while (cheeze != 0) {
			time++;
			cnt = cheeze;
			meltingCheeze();
		}
		System.out.println(time);
		System.out.println(cnt);
	}

	public static void meltingCheeze() {
		Queue<int[]> que = new LinkedList<int[]>();
		que.offer(new int[] { 0, 0 });
		v = new boolean[N][M];
		v[0][0] = true;
		while (!que.isEmpty()) {
			int[] cur = que.poll();
			for (int i = 0; i < 4; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || v[nx][ny]) continue;
				if (map[nx][ny] == 1) {
					cheeze--;
					map[nx][ny] = 0;
				} else if (map[nx][ny] == 0) {
					que.offer(new int[] { nx, ny });
				}
				v[nx][ny] = true;
			}
		}
	}
}

시간제한	메모리 제한	시간	메모리	레벨	풀이 당시 정답율
1초	128MB	104ms	15096KB	골드 5	49.16%