백준 2636번: 치즈

문제 설명

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

• NxM격자에 0 또는 1의 값이 놓여있습니다.
• 1은 치즈, 0은 공기 또는 구멍을 의미합니다.
• 공기에 닿은 면은 녹아 없어집니다.
• 치즈에 둘러쌓인 0들이 구멍입니다.

접근법

• 핵심은 공기와 구멍을 구분할 수 있어야 합니다.
  • (0,0)이 4방탐색으로 도달할 수 있는 0은 공기, 그렇지 않은 0은 구멍입니다.

pseudocode

// -1은 공기, 0은 구멍, 1은 치즈입니다.
while(처음에 치즈가 존재해야 시작할 수 있습니다){
	BFS(0,0) // (0,0)에서 도달 가능한 0을 모두 -1로 만듭니다.
    
    for(모든(i,j)를 순회하면서){
    	// 여기서의 0은 구멍의 의미는 아닙니다. 녹은 치즈를 곧바로 -1로 만들면 다른 치즈의 검사에도 영향을 주기 때문에 0으로 만들었습니다. 알고리즘에 의해 다음 검사부터 -1이 됩니다. 
    	-1과 맞닿은 1을 0으로 만듭니다. 
    }
    
    for(모든(i,j)를 순회하면서){    
    	-1을 0으로 바꿉니다. // BFS는 (0,0)에서 0을 찾도록 설계되어 있습니다. -1은 인식하지 못하기 때문에 0으로 되돌립니다.
    }
    
    if(현재 남아있는 치즈의 개수가 0개면){
    	break
    }else{
    	남아있는 치즈의 개수를 갱신합니다.
    }
}

BFS(){
	(0,0)에서 연결된 모든 0을 -1로 바꿉니다.
}

정답

import java.util.*;

class Main {
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, -1, 0, 1 };
	static int N, M, LastCheeze;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int[][] board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int val = sc.nextInt();
				board[i][j] = val;
				LastCheeze += val;
			}
		}
		
		int time = 0;
		while (LastCheeze!=0) { // 처음부터 치즈가 없다면 실행하지 말아야 합니다.
			time++;
			BFS(0, 0, board); // (0,0)과 연결된 0은 공기, 그렇지 않은 0은 구멍 // 공기를 모두 -1로 바꿉니다.
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] == 0 || board[i][j] == -1) continue; // 공기나 구멍은 패스합니다.
					// 치즈의 4방 중 한 곳이라도 공기(-1)면 해당 치즈가 녹습니다.
					for (int d = 0; d < 4; d++) {
						int nx = i + dx[d];
						int ny = j + dy[d];
						if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == -1) {
							board[i][j] = 0;
							break;
						}
					}
				}
			}

			int cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] == -1) {
						board[i][j] = 0; // 다음 BFS를 위해 -1로 바꾼 공기를 0으로 되돌립니다
					} else if(board[i][j] == 1){ // 현재 남아있는 치즈의 개수를 샙니다.
						cnt++;
					}
				}
			}
			if (cnt == 0) { // 남아있는 치즈가 없다면 while문을 종료합니다.
				break;
			} else {
				LastCheeze = cnt;
			}
		}
		System.out.println(time);
		System.out.println(LastCheeze);
	}

	public static void BFS(int x, int y, int[][] board) {
		board[x][y] = -1;
		int[] temp = { x, y };
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(temp);
		while (!q.isEmpty()) {
			int[] now = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = now[0] + dx[d];
				int ny = now[1] + dy[d];
				if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == 0) {
					board[nx][ny] = -1;
					int[] temp2 = { nx, ny };
					q.add(temp2);
				}
			}
		}
	}
}

기타

• BFS 과정에서 녹을 치즈를 판별할 수 있는데 그렇게 설계하지 않아 전체 순회를 한번 더 실행했다(비효율)
  • 공기(-1) 옆에 치즈(1)가 있으면 사라질 치즈list에 담고 탐색종료 후 한꺼번에 업데이트 해주는 방식이 가능.