BOJ_2638 : 치즈

👉 문제링크

2638번: 치즈

---

---

🔸 문제 분석 🔸

• N x M 모눈종이에 공기와 치즈가 0, 1 로 주어진다.
• 외부 공기와 2개 이상 맞닿은 치즈는 녹는다.
• 치즈가 모두 녹는데 걸리는 시간을 구한다.

🔸 문제 풀이 🔸

• 치즈 내부의 공기와 외부 공기를 분리해서 생각한다.
  • 가장자리 면은 치즈를 두지 않는다고 문제에서 제한했으므로, (0,0)부터 그래프 탐색으로 인접한 0을 2로 바꾼다.
  • 풀이에선 DFS를 사용했다.
• 공기와 맞닿은 치즈를 녹여 없앤다.
  • 치즈가 녹은 자리는 공기를 채우는데, 같은 시간에 녹는 다른 치즈들에 영향을 주지 않도록, 0으로 바꾼다.
  • 같은 시간의 모든 치즈를 확인한 뒤, 외부 공기 2와 인접한 공기 0을 모두 2로 바꾼다.
• 치즈가 모두 녹을 때 까지 반복한다.

🔸 코드 🔸

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

public class Main {
    private static final int[] dx = {-1, 0, 1, 0};
    private static final int[] dy = {0, 1, 0, -1};
    private static int N, M, map[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];

        Queue<Point> que = new ArrayDeque<>();

        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());
                if (map[i][j] == 1) que.add(new Point(i, j));
            }
        }

        air_dfs(0, 0);

        int answer = 0;

        while (!que.isEmpty()) {
            int size = que.size();

            for (int i = 0; i < size; i++) {
                Point point = que.poll();
                int cnt = 0;
                for (int j = 0; j < 4; j++) {
                    int row = point.r + dx[j];
                    int col = point.c + dy[j];
                    if (0 <= row && row < N && 0 <= col && col < M && map[row][col] == 2) {
                        cnt++;
                    }
                }
                if (cnt > 1) {
                    map[point.r][point.c] = 0;
                } else {
                    que.add(point);
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 2)
                        air_dfs(i, j);
                }
            }
            answer++;
        }

        bw.write(Integer.toString(answer));
        bw.flush();
    }

    private static void air_dfs(int r, int c) {
        map[r][c] = 2;

        for (int i = 0; i < 4; i++) {
            int row = r + dx[i];
            int col = c + dy[i];
            if (0 <= row && row < N && 0 <= col && col < M && map[row][col] == 0) {
                air_dfs(row, col);
            }
        }
    }

    private static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

🔸 코드 해석 🔸

• 좌표를 저장하기 위한 클래스 Point를 만들어 사용했다.
• DFS로 외부공기와 밀접한 공기들을 0에서 2로 만들어주는 메서드 air_dfs()를 만들어 사용했다.
• 같은 시간에 녹은 치즈를 큐를 이용해 판별한다.
  • 인접한 외부공기가 2개 이상인 치즈는 공기(0) 으로 만든다.
  • 2개 미만이라면, 치즈 상태이므로 큐에 다시 넣는다.
  • 외부 공기(2)와 인접한 공기(0)을 air_dfs() 메서드를 통해 모두 2로 만들어 준다.
  • 치즈가 모두 없어질 때 까지 반복한다.
• 치즈가 모두 녹는데 걸린 시간을 카운트한 변수 answer를 출력한다.

---

🔸 end 🔸

• 골드 3치고는 간단한 그래프 탐색 문제였다.
  • 공기 탐색은 뭐든 상관 없을 것 같아서, 구현이 비교적 간단한 DFS를 이용했다.
  • 녹은 치즈 관리는 BFS를 써야 할 줄 알았는데, 그냥 큐를 이용하는 느낌이었다.
• 인접 공기 0을 외부 공기 2로 바꿔주는 부분에서 0을 찾으면 바로 2로 바꾸도록 했는데, 치즈 속 공기까지 변해서 틀렸다.
  • 2를 찾아서 인접 0을 찾아 변경하는 방식으로 외부 공기와 인접한 0을 찾아 바꿔서 맞을 수 있었다.