백준 알고리즘 - 2636 치즈

www.acmicpc.net/problem/2636

2636번: 치즈

 

  백준 알고리즘 2636 치즈 문제입니다.

 

  여러가지 방법을 생각해보았지만 결국 전부 탐색해보는 수밖에 없다는 결론에 이르렀을 때, 그 탐색 방법으로는 BFS가 떠올랐습니다. 이 문제만의 차별점이라면 BFS 탐색을 한번만 하고 끝나는 것이 아니라 한번 마치고 해당되는 치즈들 녹이고, 또 탐색하고 해당되는 치즈들을 녹이는 등과 같이 BFS 탐색을 여러번 반복한다는 것입니다.

 

 

  아래는 제 코드입니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_2636_치즈 {

	private static int[][] input;
	private static int N, M;
							// 상, 하, 좌, 우
	private static int[] dy = {0, 0, -1, 1};
	private static int[] dx = {-1, 1, 0, 0};
	private static boolean[][] visited;
	private static int count;
	private static boolean end;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());

		input = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			tk = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < M; j++) {
				input[i][j] = Integer.parseInt(tk.nextToken());
			}
		}
		
		int limit = 0;
		while(!end) {
			visited = new boolean[N][M];
			bfs(limit++);
		}
		
		System.out.println(limit-1);
		System.out.println(count);
	}

	private static void bfs(int limit) {
		Queue<int[]> que = new ArrayDeque<int[]>();
		ArrayList<int[]> list = new ArrayList<int[]>();
		
		visited[limit][limit] = true;
		que.offer(new int[] {limit, limit});
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			int cx = cur[0];
			int cy = cur[1];
			
			for(int j = 0; j < 4; j++) {
				int ty = cy + dy[j];
				int tx = cx + dx[j];
				
				if(tx >= limit && ty >= limit && tx < N-limit && ty < M-limit) {
					// 빈 공간을 만났을 때
					if(input[tx][ty] == 0 && !visited[tx][ty]) {
						visited[tx][ty] = true;
						que.offer(new int[] {tx, ty});
					}
					// 치즈를 만났을 때
					else if(input[tx][ty] == 1 && !visited[tx][ty]) {
						visited[tx][ty] = true;
						list.add(new int[] {tx, ty});
					}
					
				}
			}
			
		}
		// list에 있는 애들 녹이기
		// 만일 list가 비어있다면 끝난 것.
		// count에 지금 녹을 치즈의 칸 수 입력
		if(list.isEmpty()) {
			end = true;
			return;
		}
		else {
			count = list.size();
			for (int[] cur : list) {
				input[cur[0]][cur[1]] = 0;
			}
		}
	}
}