백준_치즈_2636

//알고리즘

1. 탐색문제 + 약간의 아이디어

2. 치즈안에있는 0과(구멍) 치즈 밖의 공기의 구분이 필요함.

3. 가장자리에서 dfs를 돌려 공기를 방문배열에 true로 표시.

4. 가장자리에 있는 치즈 제거

5. 녹은 치즈와 0의 개수를 담는 변수 sum, cnt를 선언하여 0의 개수가 맵의 크기와 같을 때 (전부 다 녹음),

기저조건에서 결과값을 알 수 있음.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 치즈_2636 {
	static int N, M, map[][], ans, time;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		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());
			}
		}

		cal(1);
//		print(map);
		
		System.out.println(time);
		System.out.println(ans);

	}

	private static void cal(int idx) {

		int sum = 0;
		int cnt = 0;
		boolean[][] v= new boolean[N][M];
		
		dfs(0,0,v);
		
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				
				if(map[r][c]==0) {
					cnt ++;
					continue;
				} 
				
				for (int k = 0; k < 4; k++) {
					int nr = r + dr[k];
					int nc = c + dc[k];

					if (map[nr][nc] == 0 && v[nr][nc]) {
						map[r][c] = 0;
						sum++;
						cnt++;
						break;
					}
				}

			}
		}
		
		if(cnt == N*M) {
			time = idx;
			ans = sum;
			return;
		} 
		
		cal(idx+1);

	}

	private static void dfs(int r, int c, boolean[][] v) {
		v[r][c] = true;
		
		for (int k = 0; k < 4; k++) {
			int nr = r+ dr[k];
			int nc = c + dc[k];
			
			if(nr< 0 || nc < 0 || nr>= N || nc>=M) continue;
			if(map[nr][nc] == 0 && !v[nr][nc]) {
				dfs(nr,nc,v);
			}
		}
		
		
		
	}

	private static void print(int[][] map) {
		// TODO Auto-generated method stub
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

	}

}