[백준 2638] 치즈 (골드 3)

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

처음 문제를 보았을 때 아래와 같이 판단하였다.

1. BFS를 통해서 먼저 외부 공기(-1)를 구분한다.

2. 배열을 순회하면서 외부 공기랑 2면 이상 닿으면 0으로 표시한다.

3. 치즈가 없는지 판단한다.(1이 하나라도 있으면 true 반환)

 

* 문제를 풀 때, 초기화 단계를 잊어버리는 경우가 많아서 체크하기 위해 따로 적어둔다.

 

하지만 while문을 통과하지 못하는 오류가 발생하였다.

확인해보니 치즈를 녹이는 단계에서 외부 공기랑 2면 이상 닿았을 때 바로 0으로 바꾸는 것 때문에 제대로 다음 치즈들에 대해서 처리가 되지 않았다.

또한 외부 공기를 한 번 확인하고 치즈를 녹이는데 다시 외부 공기를 확인할 때 외부 공기를 다시 판단해야하는데 초기화 하지 않아서 문제가 발생한 것을 알고 코드를 다시 수정하였다.

 

최종 코드

package baekjoon._2638;

import java.util.*;
import java.io.*;
// https://www.acmicpc.net/problem/2638

public class Main {
	static int N, M;
	static int[][] map;
	static int count;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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());
			}
		}

		while (true) {
			resetAir();
			findOutsideAir(0,0);
			meltCheese();
			count++;
			if (!checkCheese()) {
				break;
			}
		}
		System.out.println(count);
		
	}
	static void findOutsideAir(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {x, y});
		
		while(!q.isEmpty()) {
			int[] node = q.poll();
			int a = node[0];
			int b = node[1];
			
			if (map[a][b] == 0) {
				map[a][b] = -1;
			}
			for (int i=0; i<4; i++) {
				int na = a +dx[i];
				int nb = b + dy[i];
				
				if (na >= 0 && nb >= 0 && na <N && nb <M && map[na][nb] != -1) {
					if (map[na][nb] == 1) {
						continue;
					} else {
						map[na][nb] = -1;
						q.add(new int[] {na, nb});
					}
				}
			}
		}
		
		
	}
	
	static void meltCheese() {
	    boolean[][] toMelt = new boolean[N][M];

	    for (int i=0; i<N; i++) {
	        for (int j=0; j<M; j++) {
	            int exposeCount = 0;
	            if (map[i][j] == 1) {
	                for (int k=0; k<4; k++) {
	                    int nx = i + dx[k];
	                    int ny = j + dy[k];
	                    if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] == -1) {
	                        exposeCount++;
	                    }
	                }
	            }
	            if (exposeCount >= 2) {
	                toMelt[i][j] = true;
	            }
	        }
	    }

	    for (int i=0; i<N; i++) {
	        for (int j=0; j<M; j++) {
	            if (toMelt[i][j]) {
	                map[i][j] = 0;
	            }
	        }
	    }
	}
	
	static boolean checkCheese() {
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				if(map[i][j] == 1) {
					return true;
				}
			}
		}
		return false;
	}
	
	static void resetAir() {
	    for (int i = 0; i < N; i++) {
	        for (int j = 0; j < M; j++) {
	            if (map[i][j] == -1) {
	                map[i][j] = 0;
	            }
	        }
	    }
	}

}