백준 2638번: 치즈

문제 설명

• https://www.acmicpc.net/problem/2638
• 외부 공기와 2칸 이상 접촉한 치즈는 1초 뒤 녹습니다. 몇초 뒤 모든 치즈가 녹는지 구하는 문제입니다.

접근법

• (0,0)부터 접근이 가능한 치즈가 아닌 공간은 모두 외부 공기 입니다.
• 외부 공기를 -1로 표현했습니다.
• 시간이 지날 때마다 (0,0)부터 DFS를 실행하면서 외부 공기(-1)를 넓혀갔습니다.

정답

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

public class Main {
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int N, M;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int[][] board = new int[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
			}
		}

		int cnt = 0;
		while(true) {
			BFS(board);
			cnt++;
			
			if(Check(board)) {
				break;
			}
		}
		System.out.println(cnt);

	}

	public static void BFS(int[][] board) {
		boolean[][] v = new boolean[N][M];
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] { 0, 0 });
		List<int[]> list = new LinkedList<int[]>();
		while (!q.isEmpty()) {
			int[] now = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = now[0] + dx[d];
				int ny = now[1] + dy[d];
				if (0 <= nx && nx < N && 0 <= ny && ny < M && !v[nx][ny]) {
					v[nx][ny] = true;
					if (board[nx][ny] != 1) {
						board[nx][ny] = -1;
						q.add(new int[] { nx, ny });
					} 
				}
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(board[i][j] == 1 && Validate(i,j,board)) {
					list.add(new int[] {i,j});
				}
			}
		}
		for (int i = 0; i < list.size(); i++) {
			int[] val = list.get(i);
			board[val[0]][val[1]] = -1;
		}

	}

	public static boolean Validate(int x, int y, int[][] board) {
		int cnt = 0;
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == -1) {
				cnt++;
			}
		}
		if (cnt >= 2) {
			return true;
		}
		return false;
	}

	public static boolean Check(int[][] board) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] != -1) {
					return false;
				}
			}
		}
		return true;
	}

}


/*
8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0
*/