boj 2638: 치즈

치즈는 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉하면 녹는다.

이 때, dfs를 돌며 바로바로 치즈를 녹이는 식으로 문제를 풀면 안되고, 미리 어떤 치즈가 녹을지 체크를 한 뒤 해당 체크 부분만 녹이도록 해야 한다.

풀이는 아래와 같다.

import java.util.*;

public class Main {
	public static int[] dr = { 0, 0, 1, -1 };
	public static int[] dc = { 1, -1, 0, 0 };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n][m];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		int time = 0;
		while (true) {
			boolean isVisited[][] = new boolean[n][m];
			boolean isMelted = false;

			dfs(0, 0, n, m, mat, isVisited);
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (mat[i][j] == 1 && meltCheese(i, j, n, m, mat)) {
						isMelted = true;
					}
				}
			}

			if (!isMelted) {
				break;
			}
			time++;
		}
		System.out.println(time);
	}

	private static void dfs(int r, int c, int n, int m, int[][] mat, boolean[][] isVisited) {
		mat[r][c] = -1;
		isVisited[r][c] = true;
		for (int i = 0; i < 4; i++) {
			int row = r + dr[i];
			int col = c + dc[i];
			if (isBoundary(row, col, n, m) && mat[row][col] != 1 && !isVisited[row][col]) {
				dfs(row, col, n, m, mat, isVisited);
			}
		}
	}

	private static boolean meltCheese(int r, int c, int n, int m, int mat[][]) {
		int airs = 0;
		for (int i = 0; i < 4; i++) {
			int row = r + dr[i];
			int col = c + dc[i];
			if (isBoundary(row, col, n, m) && mat[row][col] == -1) {
				airs++;
			}
		}
		if (airs >= 2) {
			mat[r][c] = 0;
			return true;
		}
		return false;

	}

	private static boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow) {
			return false;
		}
		if (col >= maxCol) {
			return false;
		}
		return true;
	}
}