[백준/boj] 2636: 치즈 (Java) / BFS

문제

2636번: 치즈

설명

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] map;
	static boolean[][] visited;
	static int time, cnt, preCnt, N, M;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {-1,1,0,0};
	
	static private class Pos{
		int x;
		int y;
		
		Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws Exception {
		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());
			}
		}
		time =0; cnt =0; preCnt =0;
		while(true) {
			visited = new boolean[N][M];
			cnt = bfs();
			if(cnt == 0) break;
			preCnt = cnt;
			time++;
		}
		System.out.println(time);
		System.out.println(preCnt);
	}
	private static int bfs() {
		int cnt = 0, nx, ny, x, y;
		Deque<Pos> deque = new ArrayDeque<Pos>();
		deque.add(new Pos(0,0));
		while(!deque.isEmpty()) {
			Pos pos = deque.poll();
			x = pos.x;
			y = pos.y;
			for(int i=0;i<4; i++) {
				nx = x + dx[i];
				ny = y + dy[i];
				if(!isRange(nx,ny) || visited[nx][ny]) continue;
				if(map[nx][ny] == 0) {
					visited[nx][ny] = true;
					deque.add(new Pos(nx, ny));
				} else if(map[nx][ny] == 1) {
					cnt++;
					map[nx][ny] = 0;
					visited[nx][ny] = true;
				}
			}
		}
		return cnt;
	}
	
	private static boolean isRange(int x,int y) {
		return x < 0 || x>= N|| y <0 || y >=M ? false : true;
	}
}

int[][] map

• 먼저 가장자리에는 치즈가 놓여있지 않기 때문에 항상 (0,0)에서 탐색을 시작하도록 했다. 

map[nx][ny] 가 0 => deque에 담는다(이후에 사방 탐색을 진행한다.)
map[nx][ny] 가 1 => 치즈를 녹인다(cnt++, map[nx][ny] = 0), deque에 담지 않는다.
    이때, deque에 담지 않는 이유는 치즈를 녹인 위치를 deque에 담으면 가장자리가 아닌부분까지 탐색하게 되기 때문이다.

• 이렇게 한번의 bfs를 돌면 가장자리의 치즈만 녹고, 녹인 치즈 개수(cnt)를 알 수 있다. cnt를 반환한다.
• 반환된 cnt == 0 이라는 것은 모든 치즈가 녹았음을 의미하기 때문에 break 해준다.

cnt > 0 이라면 이전에 녹인 치즈 개수(preCnt)를 방금 녹인 치즈 개수로 갱신하고, time을 한시간 늘린다음 다시 bfs를 실행한다.

• preCnt에는 마지막으로 녹인 치즈 개수가 들어있을 것이다. time과 preCnt를 출력하면 끝!