[BOJ] 백준 2638번 치즈 (Java)

#2638 치즈

난이도 : 골드 4

유형 : 그래프 / BFS / DFS

2638번: 치즈

▸ 문제

N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 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은 하나의 공백으로 분리되어 있다.

▸ 출력

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

 

문제 풀이  

그래프 시뮬레이션 문제로 조건에 따라 설계를 잘해줘야 하고 헷갈리지 않게 인덱싱을 해주는 것이 중요하다.

 

구상

일단 그래프 탐색을 하기 전에 외부 공기와 내부 공기를 구분지어준다. 인접한 공기들을 인덱싱해줘야하므로 BFS탐색을 사용한다. 왜냐하면 치즈는 외부의 공기에 의해서만 녹기 때문이다. 내부 공기는 치즈 녹이는 것과는 상관없기 때문에 한 싸이클이 돌기 전까지 그냥 냅둔다. 나중에 구멍이 생기면 그때 갱신해주면 된다.

 

그 이후에 이제 외부 공기에 마찰이 된 면적이 2개이상인 치즈들을 선별해준다. 이때는 DFS탐색을 사용하는 것이 좋을 것 같다. 왜냐하면 비교적 그래프 면적에 비해 치즈인 부분은 싸이클이 갈수록 줄어들기 때문에 BFS로 인접탐색을 하는 것보다 치즈인 곳을 찾아서 이어진 부분을 깊게 탐색해주는 것이 좋을 것 같다고 생각이 들었다.

 

그렇게 마찰이 2개이상 되어있는 치즈들을 골라줬으면 한꺼번에 업데이트 시켜준다. 여기서 매 탐색마다 갱신해주면 안된다. 그러면 한 싸이클에서 이전에 녹은 치즈 공간을 외부공기로 착각할 수도 있기 때문이다. 이런 문제는 인덱싱을 잘해줘야한다.

 

 

설계

1. 싸이클을 시작한다. 더이상 녹일 치즈가 없을 때 까지 반복해준다.
   1. 외부 공기와 내부 공기를 구분지어준다. BFS탐색으로 외부공기는 9로 내부공기는 0으로 인덱싱해준다. outsideAirIndexing();
   2. 치즈인 곳을 찾아 DFS탐색으로 외부공기와 마찰이 2개이상인 치즈를 선별해준다. if(map[y][x] ==1 && isAvailableMelt(x, y))
      1. 일단 해당 치즈들은 -1로 인덱싱해준다. map[y][x] = -1;
   3. 녹일 치즈가 없다면 싸이클을 종료한다. if(cnt==0) break;
   4. -1로 되어있는 치즈들을 한꺼번에 외부공기 9로 바꿔준다. mapUpdate();
   5. 다시 1번으로 돌아가서 반복해준다.
2. 싸이클이 종료되면 싸이클을 돌린 횟수를 출력해준다.

 

풀이 코드 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int n,m;
	static boolean[][] checked;
	static int[][] map;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException{
		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());
			}
		}
		
		map[0][0] = 9;
		int cycle =0;
		while(true) {
			outsideAirIndexing();
			
			checked = new boolean[n][m];
			int cnt=0;
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					if(map[i][j] == 1 && !checked[i][j]) {
						cnt += melting(j,i);
					}
				}
			}
			
			if(cnt ==0) break;
			mapUpdate();
			
			cycle++;
		}
		System.out.println(cycle);
	}
	
	static void mapUpdate() {
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j] == -1) {
					map[i][j] = 9;
				}
			}
		}
	}
	
    // 외부공기 인덱싱 해주기 
	static void outsideAirIndexing() {
		Queue<int[]> q = new LinkedList<>();
		checked = new boolean[n][m];
		
		q.add(new int[] {0,0});
		checked[0][0] = true;
		
		while(!q.isEmpty()) {
			int[] pos = q.poll();
			int px = pos[0], py = pos[1];
			
			for(int i=0; i<4; i++) {
				int nx = px + dx[i];
				int ny = py + dy[i];
				
				if(nx<0 || nx>m-1 || ny<0 || ny>n-1 || checked[ny][nx]) continue;
				
				if(map[ny][nx] != 1) {
					map[ny][nx] = 9;
					checked[ny][nx] = true;
					q.add(new int[] {nx, ny});
				}
			}
		}
	}
	
    // 치즈 녹이기 
	static int melting(int x, int y) {
		checked[y][x] = true;
		if(map[y][x] ==1 && isAvailableMelt(x, y))	{
			map[y][x] = -1;
			return 1;
		}
		
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx<0 || nx>m-1 || ny<0 || ny>n-1 || checked[ny][nx]) continue;
			
			if(map[ny][nx] == 1) {
				melting(nx, ny);
			}
		}
		return 0;
	}
	
    // 해당 치즈 외부마찰2개 이상인지 확인 
	static boolean isAvailableMelt(int x, int y) {
		int cnt =0;
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx<0 || nx>m-1 || ny<0 || ny>n-1) continue;
			if(map[ny][nx] == 9) cnt++;
		}
		
		if(cnt>=2) return true;
		return false;
	}
}