[Java] 백준 2638번 : 치즈

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

예제 입력 1

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

예제 출력 1

4

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, M, cnt=0;
	private static int[][] graph;
	private static int []dx= {-1,1,0,0};
	private static int []dy= {0,0,-1,1};

	static class Point {
		int r, c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}

	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		graph = new int[N][M];

		for (int r = 0; r < N; r++) {
			st = new StringTokenizer(br.readLine());
			for (int c = 0; c < M; c++) {
				graph[r][c] = Integer.parseInt(st.nextToken());
				if(graph[r][c]==1) {
					graph[r][c]=-1;	// 치즈가 있는 곳을 -1로 바꿔줌
					cnt++;	// 치즈의 개수를 셈
				}
			}
		}
		int depth=0;	// 치즈가 다 녹는데 걸리는 시간을 재기 위해 depth를 선언함
		while(cnt>0) {	// 치즈의 개수가 양수이면 반복문 수행
			depth++;
			bfs();	// bfs를 통해 녹일 치즈를 찾으러 감
		}
		System.out.println(depth);
	}

	private static void bfs() {	// 녹게 되는 치즈를 탐색
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(0, 0));

		boolean [][]visited=new boolean[N][M];
		visited[0][0]=true;
		
		while(!queue.isEmpty()) {
				Point p=queue.poll();
				
				for(int d=0;d<4;d++) {
					int nx=p.r+dx[d];
					int ny=p.c+dy[d];
					
					if(isIn(nx, ny)) {
						if(graph[nx][ny]==-1) graph[nx][ny]=1;	// 처음 접하는 치즈이면 1로 세팅
						else if(graph[nx][ny]>0) graph[nx][ny]++;	// 이미 접한 치즈이면 방문값 증가시킴
						else {	// 치즈가 아니면 방문 처리 후 큐에 넣어줌
							if(!visited[nx][ny]) {
								visited[nx][ny]=true;
								queue.add(new Point(nx, ny));
							}
						}
					}
				}
		}
		melt();	// 치즈를 녹임
	}
	
	private static void melt() {
		for(int r=0;r<N;r++) {
			for(int c=0;c<M;c++) {
				if(graph[r][c]>=2) {	// 공기와 2면 이상 접한 경우 녹아서 0으로 세팅함
					graph[r][c]=0;
					cnt--;	// 녹은 치즈의 개수를 빼줌
				} else if(graph[r][c]==1) graph[r][c]=-1;	// 공기와 1면만 접한 경우 다시 -1로 설정
			}
		}
	}
	private static boolean isIn(int r, int c) {
		return r>=0 && r<N && c>=0 && c<M;
	}
}

치즈 내부의 공간은 외부 공기와 접촉하지 않은 것으로 가정하기 위해 공기부터 bfs 탐색을 해야하는 점이 색다른 문제였습니다.

1. 치즈를 전부 -1로 처리하고 전체 치즈의 개수를 미리 저장해둠

2. bfs를 돌며 공기와 2면 이상 접촉한 치즈를 구함

3. 치즈를 녹이고, 남은 치즈를 다시 -1로 처리함

4. 치즈가 다 녹을 때까지 위 과정을 반복함