BOJ_2636 치즈 [Java] (G5)

문제 설명

풀이

기본적으로 BFS로 풀어야된다는 것을 알고 있어야 한다.

그리고 생각보다 안복잡하고 간단한데, 안에 있는 공기는 신경안 써도 되는게, 밖에 있는 공기를 기준으로 BFS를 돌리면 된다는 것이다.

밖에 있는 빈칸을 기준으로 BFS를 돌리고, 경계면에 있는 치즈를 바로 0으로 바꿔주면서, 계속 Roop 시키면 끝!

 

배운것 : 복잡하게 생각하지 말고, 천천히 생각해보자

 

코드

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

public class Main {
	public static int N, M, cheese, 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)
					cheese++;
			}
		}
		while (cheese != 0) {
			time++;
			cnt = cheese;
			meltingCheese();
		}
		System.out.println(time);
		System.out.println(cnt);
	}

	public static void meltingCheese() {
		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) {
					cheese--;
					map[nx][ny] = 0;
				} else if (map[nx][ny] == 0) {
					que.offer(new int[] { nx, ny });
				}
				v[nx][ny] = true;
			}
		}
	}
}