[백준_2636번] 치즈

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

2636번: 치즈

[문제]

 아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

 

<그림 1> 원래 치즈 모양

 

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

 

<그림 2> 한 시간 후의 치즈 모양

 

<그림 3> 두 시간 후의 치즈 모양

 

 <그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

 입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

 

[코드]

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

class Cheese_2636 {
	int x;
	int y;
	
	public Cheese_2636(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_2636 {
	public static int n,m,totalcheese,count,time;
	public static int[][] map;
	public static boolean[][] visited;
	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		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());
				if (map[i][j]==1)
					totalcheese++;
			}
		}
		
		while(totalcheese!=0) {
			time++;
			/*
			 * 치즈가 모두 없어지기 1시간 전의 개수를 구해야하므로
			 * 마지막 bfs 함수가 수행되기 전의 전체 치즈의 개수를 저장해줘야 한다. 
			 */
			count=totalcheese;
			bfs();
		}
		
		System.out.println(time);
		System.out.println(count);
	}

	public static void bfs() {
		Queue<Cheese_2636> que = new LinkedList<>();
		que.offer(new Cheese_2636(0,0));
		visited=new boolean[n][m];
		visited[0][0]=true; // (0,0)부터 시작
		
		while (!que.isEmpty()) {
			Cheese_2636 ch=que.poll();
			
			// 상,하,좌,우 탐색
			for(int i=0;i<4;i++) {
				int nx=ch.x+dx[i];
				int ny=ch.y+dy[i];
				
				// 이동 좌표가 범위를 벗어나거나 방문한 좌표라면 넘어간다.
				if (nx<0||nx>=n||ny<0||ny>=m||visited[nx][ny]) 
					continue;
				
				// 이동한 좌표에 치즈가 있다면
				if(map[nx][ny]==1) {
					totalcheese--; // 전체 치즈개수에서 1 감소
					map[nx][ny]=0; // 치즈 제거
				} 
				/*
				 * 치즈는 공기와 맞닿은 부분이 제거되야 한다.
				 * 따라서 이동한 좌표가 공기라면 큐에 넣고 상,하,좌,우를 탐색해주고,
				 * 그 중 치즈가 있다면 없어져야하는 치즈이기 때문에 위의 코드를 실행해준다.
				 */
				else if(map[nx][ny]==0) {
					que.offer(new Cheese_2636(nx,ny));
				}
				visited[nx][ny]=true; // 방문처리
			}
		}
	}
}

 

[고찰]

 이번 문제는 어떻게 공기와 맞닿아 있는 치즈를 판별해야 할까 고민을 해봤지만 해결 방법이 떠오르지 않아 다른 사람의 코드를 참고하여 해결하였다. 결론을 말하자면 공기와 맞닿아 있는 치즈를 찾을 필요가 없다.  

 제거되어야 하는 치즈는 공기와 맞닿아 있는 부분으로, 공기 좌표를 기준으로 상, 하, 좌, 우를 탐색하여 치즈가 있다면 제거하면 된다. 이렇게 동작하기 위해서는 큐에 치즈가 아닌 공기의 좌표를 삽입해야 한다. 공기의 좌표를 삽입하게 되면 공기를 기준으로 4방향을 탐색하기 때문에 탐색 도중에 치즈를 발견한다면 해당 치즈는 무조건 공기와 맞닿아 있는 치즈일 수 밖에 없기 때문이다. 이 부분을 생각하지 못했다. 아직 공부가 더 필요한 것 같다.