[BaekJoon] 2638번 치즈 (Java) 문제 풀이 [Gold 3]

문제

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

2638번: 치즈

 

어떻게 풀 것인가?

이 문제는 (0, 0)에서 bfs를 실행하여 문제에서 주어진 그림 1, 2, 3과 같이  바깥공기와 2면 이상이 닿은 치즈들을 녹이면서 몇 초 후에 치즈가 전부 없어지는지 구하는 문제이다.

여기서 유의해야할 점은 바깥공기와 내부의 밀폐된 공기를 구분해야한다.

-1 인 곳 : 바깥 공기가 존재하는 곳

0인 곳 : 안쪽 공기가 존재하는 곳

1인 곳 : 치즈가 존재하는 곳

이런식으로 3개의 영역을 구분하면 문제가 훨씬 쉽게 접근이 가능하다.

그래서 나는 BFS를 통해서 3개의 영역을 구분하였고, 치즈의 갯수를 차례로 삭제 하였다.

 

풀면서 놓쳤던점

바깥공기와 내부공기(?) 를 나눠야 하는 것에서 조금 어려웠다.

 

 

이 문제를 통해 얻어갈 것

BFS의 활용, 다른 사람들의 풀이를 확인해보니 DFS와 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;

// 백준알고리즘 2638번 치즈
public class Main {
    static int N, M;
    static int[][] map;
    static int[][] air;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result = 0, cheeseNum = 0;

    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());

        map = new int[N][M];
        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)
                    cheeseNum++;
            }
        }

        while (cheeseNum != 0) BFS();

        System.out.println(result);

    }


    static void BFS() {
        air = new int[N][M];

        Queue<Node> que = new LinkedList<>();
        que.offer(new Node(0, 0));
        air[0][0] = -1;

        while (!que.isEmpty()) {
            Node a = que.poll();

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

                if (range(nx, ny))
                    continue;

                if (map[nx][ny] == 1)
                    air[nx][ny]++;
                if (map[nx][ny] == 0 && air[nx][ny] == 0) {
                    air[nx][ny] = -1;
                    que.offer(new Node(nx, ny));
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (air[i][j] >= 2) {
                    cheeseNum--;
                    map[i][j] = 0;
                }
            }
        }
        result++;
    }

    public static boolean range(int x, int y) {
        return x < 0 || x >= N || y < 0 || y >= M;
    }
}

class Node {
    int x, y;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

참고

X