[백준 / Java] 2636: 치즈 (BFS)

난이도: Gold 4

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

 

겉에 있는 치즈부터 녹여서 치즈를 점점 안쪽으로 녹이면 되는 문제이다.

 

 

초기 배열은 이렇다.

세로(N) * 가로(M) 크기의 2차원 배열을 선언해주어야 한다.

 

 

치즈는 이렇게 겉에 있는 것만 녹이면 된다고 한다.

나는 이 문제를 0주변에 있는 1들을 없애면 되는게 아닌가 했는데, 가운데에도 0이 있다.

겉에 있는 0 주변에 있는 1들만 없애야 한다.

 

가운데에 있는 0은 제외하고 겉에 있는 0 주변에 있는 1을 없애야 한다.

이렇게 하려면 어떻게 해야할까?

 

일단 공기 칸을 체크할 2차원 배열을 만든다.

겉에 있는 0들을 bfs를 사용해서 공기 칸을 체크할 배열을 true로 체크하면 된다.

그리고, true로 체크된 칸 주변에 있는 1들도 bfs를 사용해서 없애면 된다.

이때는 2차원 visited 배열도 만들어서 같은 칸을 계속 빙빙 돌지 않게 해야 한다.

1을 없앨 때에는 1이 있던 칸을 0으로 만들면 된다.

 

 

위와 같이 true 주변에 1이 있던 칸을 0으로 만들고,

bfs 수행이 끝난 뒤 남은 1의 개수를 세어서 리턴해주면 된다.

모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 변수를 만들어서

리턴한 값을 이 변수에 대입하면 된다.

이렇게 하면 모든 치즈가 녹았을 경우(모든 칸이 0인 경우)에는 1의 개수를 리턴하지 않고

전에 저장되어있던 값을 출력하면 된다.

 

 

여기서 주의할 점이 있다.

치즈가 한 시간만에 녹을 수도 있다.

이럴 경우를 대비해 배열을 초기화할 때 1의 개수를 처음부터 세어서,

모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 변수에 값을 할당해주어야 한다.

그렇지 않으면 95퍼에서 틀렸습니다가 뜨게 된다.

 

 

내 코드는 상당히 지저분할 수 있다.

그래도 주석에 설명을 한 줄 한 줄 자세히 적어놓았다.

자, 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class P2636_치즈 {
    static int N, M;                    // 판의 세로, 가로 길이
    static int[] dx = {-1, 0, 1, 0};    // 상, 하 이동
    static int[] dy = {0, -1, 0, 1};    // 좌, 우 이동
    static int[][] board;                // 2차원 사각형 판 배열
    static boolean[][] air;                // 2차원 공기 배열
    static boolean[][] visited;            // 2차원 방문 배열
    static int allMeltingTime = 0;        // 치즈가 모두 녹아서 없어지는 데 걸리는 시간
    static Queue<int[]> queue = new LinkedList<>();    // bfs 수행을 위한 큐
    
    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());
        board = new int[N][M];
        int beforeMeltingCount = 0;    // 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수
        
        // 2차원 사각형 판 초기화
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                // 0: 치즈가 없는 칸, 1: 치즈가 있는 칸
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 1) {    // 해당 칸에 치즈가 있다면
                    // 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 1 증가
                    // 치즈가 한 시간만에 녹을 수도 있으므로 처음부터 개수를 세어야 함
                    beforeMeltingCount++;    
                }
            }
        }
        
        // 치즈가 모두 녹을 때까지 반복
        while (true) {
            air = new boolean[N][M];        // 공기 배열 초기화
            visited = new boolean[N][M];    // 방문 배열 초기화
            
            searchAir();    // 첫번째 공기 칸 찾기
            int count = searchMeltingCheese();    // 치즈가 녹고 남아있는 치즈조각 개수
            
            if (count == -1) {    // count 리턴 값이 -1이라면
                break;            // 치즈가 모두 녹은 것이므로 반복문 탈출
            } else {            // count 리턴 값이 -1이 아니라면
                // 치즈가 녹고 남아있는 치즈조각 개수를 
                // 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 변수에 대입
                beforeMeltingCount = count;        
            }
        }
        
        // 치즈가 모두 녹아서 없어지는 데 걸리는 시간 출력
        System.out.println(allMeltingTime);        
        // 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 출력
        System.out.println(beforeMeltingCount);
    }
    
    // 첫번째 공기 칸을 찾는 메소드
    public static void searchAir() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0) {        // 0인 칸이면 공기 칸
                    searchAirBfs(i, j);        // 해당 칸부터 모든 공기 칸을 찾기 
                    return;                    // 첫번째 공기 칸을 찾았으면 함수 종료
                }
            }
        }
    }
    
    // 모든 공기 칸을 찾는 메소드
    public static void searchAirBfs(int a, int b) {    
        queue.add(new int[] {a, b});    // 첫번째 공기 칸을 큐에 삽입    
        air[a][b] = true;                // 공기 배열 체크
        
        while (!queue.isEmpty()) {
            int[] now = queue.poll();        // 현재 공기 칸
            
            for (int i = 0; i < 4; i++) {
                int x = now[0] + dx[i];        // 현재 칸을 기준으로 x좌표 이동
                int y = now[1] + dy[i];        // 현재 칸을 기준으로 y좌표 이동
                
                // 인덱스가 유효한 범위가 아니라면 건너뛰기
                if (x < 0 || y < 0 || x >= N || y >= M) {
                    continue;
                }
                
                // 이미 공기 배열이 체크되어있거나, 치즈가 있는 칸이라면 건너뛰기
                if (air[x][y] || board[x][y] == 1) {
                    continue;
                }
                
                queue.add(new int[] {x, y});    // 이동 가능한 공기 칸을 큐에 삽입
                air[x][y] = true;                // 공기 배열 체크
            }
        }
    }
    
    // 공기인 칸을 찾아서 그 칸부터 bfs를 수행하고, 치즈가 녹고 남아있는 치즈조각 개수를 리턴하는 메소드
    public static int searchMeltingCheese() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (air[i][j]) {        // 공기 배열이 체크되어있다면 첫번째 공기 칸
                    // 공기인 칸을 기준으로 치즈를 녹이고, 치즈가 녹고 남아있는 치즈조각 개수를 리턴
                    return searchMeltingCheeseBfs(i, j);    
                }
            }
        }
        return -1;    // return 문을 2개 써주어야 해서 의미없이 작성 (쓸모없는 코드)
    }
    
    // 공기인 칸 기준에 치즈가 있으면 녹이고, 치즈가 녹고 남아있는 치즈조각 개수를 리턴하는 메소드
    public static int searchMeltingCheeseBfs(int a, int b) {
        queue.add(new int[] {a, b});    // 첫번째 공기 배열 체크된 칸을 큐에 삽입    
        
        while (!queue.isEmpty()) {
            int[] now = queue.poll();        // 현재 공기 배열 체크된 칸
            
            for (int i = 0; i < 4; i++) {
                int x = now[0] + dx[i];        // 현재 칸을 기준으로 x좌표 이동
                int y = now[1] + dy[i];        // 현재 칸을 기준으로 y좌표 이동
                
                // 인덱스가 유효한 범위가 아니라면 건너뛰기
                if (x < 0 || y < 0 || x >= N || y >= M) {
                    continue;
                }
                
                // 치즈가 있는 칸이고, 방문이 체크되어있지 않다면
                if (board[x][y] == 1 && !visited[x][y]) {
                    board[x][y] = 0;        // 치즈를 녹이기
                    visited[x][y] = true;    // 방문 체크
                }
                
                // 공기 배열 체크된 칸이고, 방문이 체크되어있지 않다면
                if (air[x][y] && !visited[x][y]) {
                    queue.add(new int[] {x, y});    // 이동 가능한 공기 칸을 큐에 삽입 
                    visited[x][y] = true;            // 방문 체크
                }
            }
        }
        
        allMeltingTime++;    // 치즈를 녹이고 1시간 경과되었으므로 시간 1 증가
        
        boolean isAllMelting = true;    // 치즈가 모두 녹았는지의 여부
        int count = 0;                    // 치즈가 녹고 남아있는 치즈조각 개수
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 1) {        // 해당 칸에 치즈가 있다면
                    count++;                // 치즈가 녹고 남아있는 치즈조각 개수 1 증가
                    isAllMelting = false;    // 치즈가 모두 녹지 않았으므로 false로 바꾸기
                }
            }
        }
        
        if (isAllMelting) {    // 치즈가 모두 녹았다면
            return -1;        // -1 리턴
        } else {            // 치즈가 모두 녹지 않았다면
            return count;    // 치즈가 녹고 남아있는 치즈조각 개수 리턴
        }
    }
}