BOJ_2636 : 치즈

👉 문제링크

2636번: 치즈

---

---

🔸 문제 분석 🔸

• H x W 격자 판에 치즈가 있다.
  • 치즈는 가장자리에 놓이지 않는다.
  • 공기와 접촉한 치즈는 한 시간 뒤 녹아 없어진다.
  • 치즈 안에는 1개 이상의 구멍이 있다.
  • 구멍 안의 공기는 외부 공기와 접촉하기 전까진 치즈를 녹이지 않는다.
  • 치즈가 모두 녹아 없어지는 데 까지 걸린 시간과 직전 치즈 개수를 출력한다.
• 그래프 탐색이므로 BFS혹은 DFS를 사용한다.

🔸 코드 🔸

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 Main {
    private static class Point {
        int r, c;

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

    private static int H, W;
    private static int[][] map;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static boolean[][] visited;
    private static Queue<Point> que;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        map = new int[H][W];

        int cheese = 0;
        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < W; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) cheese++;
            }
        }

        // DFS
        que = new LinkedList<>();
        visited = new boolean[H][W];
        dfs(0, 0);

        // BFS
        int cnt = 0, size = 0;
        while (!que.isEmpty()) {
            cheese -= size;
            size = que.size();
            cnt++;
            for (int i = 0; i < size; i++) {
                Point point = que.poll();
                int r = point.r;
                int c = point.c;
                map[r][c] = 2;
                for (int j = 0; j < dx.length; j++) {
                    int x = point.r + dx[j];
                    int y = point.c + dy[j];
                    if (0 <= x && x < H && 0 <= y && y < W) {
                        if (map[x][y] == 1 && !visited[x][y]) {
                            visited[x][y] = true;
                            que.add(new Point(x, y));
                        }
                        else if(map[x][y] == 0)
                            dfs(x, y);
                    }
                }
            }
        }

        // Output
        System.out.println(cnt);
        System.out.println(cheese);
    }

    private static void dfs(int r, int c) {
        map[r][c] = 2;
        for (int i = 0; i < dx.length; i++) {
            int x = r + dx[i];
            int y = c + dy[i];

            if (0 <= x && x < H && 0 <= y && y < W) {
                if (map[x][y] == 1 && !visited[x][y]) {
                    visited[x][y] = true;
                    que.add(new Point(x, y));
                } else if (map[x][y] == 0) {
                    dfs(x, y);
                }
            }
        }
    }
}

🔸 코드 해석 🔸

• 녹기 직전 치즈는 큐에 담는다.
  • 처음 외부 공기와 맞닿은 치즈를 녹여야 한다.
  • dfs로 0,0 부터 맞닿은 공기를 모두 탐색해서, 그 주변의 치즈를 큐에 담는다.
  • 확인한 공기는 더이상 치즈를 녹일 일이 없으므로 2를 저장해둔다.
• 큐가 빌때까지 계산을 반복한다.
  • 큐 사이즈 만큼 반복하며 녹일 치즈를 꺼낸다.
  • 녹은 치즈 자리에도 2를 저장한다.
  • 주변에 치즈가 있으면 다음에 녹일 것이므로 큐에 담는다.
  • 주변에 공기가 있다면 치즈를 녹일 상태가 된 것이므로 dfs로 인접한 공기를 모두 찾아 녹일 치즈를 큐에 담는다.
• 계산을 반복한 후 경과 시간과 직전 치즈 개수를 출력한다.
  • 치즈 개수는 처음 입력 시 카운트했다가, 큐에서 녹일 치즈를 꺼낼 때 마다 차감한다.

---

🔸 end 🔸

• BFS와 DFS를 둘 다 사용해서 풀이했지만, BFS로만 통일해서 풀었어도 좋았을 것 같다.