[Algorithm] 백준 2638 치즈 java

문제

N*M의 모눈종이 위에 치즈가 표시되어있고, 이 외의 빈칸은 공기이다. 이때 실내 온도의 공기와 접촉한 치즈는 한 시간만에 녹아버린다. 이때 치즈 내부에 존재하는 빈 공간은 외부 공기와 접촉하지 않은 것으로 가정한다. 또, 모눈종이의 맨 가장자리는 치즈가 놓이지 않음!
이때 주어진 치즈가 모두 녹는데 걸리는 정확한 시간을 출력하시오~

문제 포인트

문제를 꼼꼼히 읽자..
치즈 내부에 존재하는 빈 공간과 외부 공기를 따로 구분해주고, 치즈가 녹을 때마다 빈 공간인지 외부 공기인지를 체크해줘야했다.
문제 다 풀고 봐서 다시 풀었다
ㅋ

풀이 방식

사용한 자료구조

• int[][] board: 전체 모눈종이
• boolean[][] visited: dfs 방문 체크
• int count: 전체 치즈의 개수
• int answer: 치즈가 녹는데 걸리는 시간

전체 흐름

1. 2차원 board 배열에 적절한 값을 넣는다.
   입력을 받으면서 전체 치즈의 개수를 세서 count에 넣어준다.
2. 내, 외부 공기를 구분해서 따져야하기 때문에 각각 다른 값으로 구분해줘야한다.
   녹은 치즈가 3인 이유는 아래에서..

   내부 공기 - 0
   치즈 - 1
   외부 공기 - 2
   녹은 치즈 - 3

3. checkExternal() 함수로 외부 공기를 체크해준다.
   해당 함수는 dfs로 동작하고, 이미 방문했거나 치즈인 경우를 제외한 칸 중에 외부와 접촉한 공기는 2로 표시한다.
   ---- 일단 여기까지가 기본 초기화 과정이라고 생각하면 된다.
4. 아까 count에 전체 치즈 개수를 입력받았으니, 0이 될때까지 dfs를 반복하면서 치즈를 녹이고 시간을 카운트한다.
5. dfs()에서는 녹을 가능성이 있는 치즈를 3으로 바꿔주고 count-- 해주면서 치즈의 개수를 줄여준다.

   왜 3으로 바꿔주느냐?!
   => 바로 외부 공기인 2값으로 바꿔주면 한 시간 안(이번 텀)에 녹지 말아야 할 치즈가 녹아버림

6. 윗 단계에서의 녹을 가능성의 체크는 isMelt()함수로 한다.
   이것도 dfs로 동작하고, 단순하게 네 방향을 체크하면서 외부 공기와 맞닿은 부분이 2개보다 많은 경우 true를 반환한다.
7. 치즈를 녹이는 dfs함수가 끝나면, 이때 3으로 표시했던 녹았던 치즈를 다시 2로 바꿔준다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2638 {
    static int n, m, count, answer;
    static int[][] board;
    static boolean[][] visited;
    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());
        count = 0;
        answer = 0;

        board = new int[n][m];
        visited = new boolean[n][m];

        // 치즈 1
        // 바깥 공기 2
        // 내부 공기 0
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int value = Integer.parseInt(st.nextToken());
                board[i][j] = value;

                if (value == 1) count++;
            }
        }

        checkExternalAir(0, 0);

        while (count != 0) {
            visited = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (board[i][j] == 1 && !visited[i][j]) dfs(i, j);
                }
            }

            visited = new boolean[n][m];
            checkExternalAir(0, 0);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    board[i][j] = board[i][j] == 3 ? 2 : board[i][j];
                }
            }

            answer++;
        }

        System.out.println(answer);
    }

    // 외부와 접촉한 공기 '2'로 표시
    static void checkExternalAir(int x, int y) {
        visited[x][y] = true;
        board[x][y] = 2;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny] || board[nx][ny] == 1) continue;

            board[nx][ny] = 2;
            checkExternalAir(nx, ny);
        }
    }

    static void dfs(int x, int y) {
        visited[x][y] = true;

        if (board[x][y] == 1 && isMelt(x, y)) {
            --count;
            board[x][y] = 3; // 녹은 치즈는 3으로 바꿔준다 (0으로 바꾸면 언제 녹았는지 구분 불가)
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny] || board[nx][ny] == 0) continue;

            dfs(nx, ny);
        }
    }

    static boolean isMelt(int x, int y) {
        int air = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (board[nx][ny] == 2) ++air;
        }

        return air >= 2;
    }
}