[BOJ] 2636 치즈 BFS버전 (Java)

https://www.acmicpc.net/problem/2636

알고리즘

BFS

풀이

1. 처음 상태의 판에서 치즈 개수를 구한다.
2. 테두리를 녹이기 전 상태에서 치즈 수를 구한다.
3. 테두리 치즈부터 BFS를 수행한다.
4. 테두리를 녹이고 한시간을 증가시킨다.
5. 더 이상 녹일 치즈가 없을 때까지 반복한다.

코드

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

public class Main {

	static int N, M, answer, count, cheese;
	static int[][] pan;
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, 1, 0, -1};
	static Queue<int[]> q;
	static boolean[][] v;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		pan = new int[N][M];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				pan[i][j] = Integer.parseInt(st.nextToken());
				if(pan[i][j] == 1) cheese++;
			}
		}
		
		while(cheese != 0) {					// 녹을 치즈가 없을 때까지 반복
			answer++;							// 한시간이 지남 
			count = cheese;						// 치즈 개수를 count에 저장
			bfs();								// 테두리에 있는 치즈를 녹이는 bfs 진행 
		}
		
		System.out.println(answer);
		System.out.println(count);
		br.close();
	}

	private static void bfs() {
		Queue<int[]> q = new ArrayDeque<>();	// bfs를 위한 큐 생성
		v = new boolean[N][M];					// 방문처리를 위한 boolean 배열 생성 
		q.offer(new int[] {0, 0});				// 0,0 인덱스를 큐에 넣어주고 
		v[0][0] = true;							// 0,0 방문처리 
		while(!q.isEmpty()) {
			
			int cur[] = q.poll();				// 큐에서 인덱스 하나를 꺼내고
			int y = cur[0];
			int x = cur[1];
			
			for(int d=0; d<4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];
				
				if(ny<0||ny>=N || nx<0||nx>=M || v[ny][nx]) continue;	// 범위 밖이거나, 이미 방문된 인덱스는 스킵

				if(pan[ny][nx]==1) {				// 만약 치즈라면 녹이고, 치즈 개수 감소시킴 
					pan[ny][nx] = 0;
					cheese--;
				} else q.offer(new int[] {ny, nx});	// 만약 치즈가 아니라면 큐에 추가(겉에 있는 치즈들부터 녹이기 위함)
				
				v[ny][nx] = true;					// 해당 인덱스 방문처리(방문한 곳은 위 로직을 실행시키지 않기 위함)
			}				
		}
	}
}