백준: 2638번 (치즈) [JAVA]

문제 링크

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

2638번: 치즈

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 우선 주어진 데이터를 저장할 2차원 배열 초기화
2. 외부와 접촉한 공기를 체크하는 BFS 함수를 통해 2차원 배열에 표시
3. 전체 2차원 배열 속 녹을 수 있는 치즈 좌표를 큐에 저장한 후, 전체 큐 속 치즈 좌표들을 공기로 바꾸며 추가적인 외부와 접촉한 공기 표시 작업을 진행
4. 3번의 과정을 전체 while문으로 돌며 그 때마다 answer 값 +1
5. 최종 answer 값 출력

 크게 보면 단순 BFS 기반 함수인 것 같지만 치즈가 녹는 조건, 외부와 접촉한 공기와 접촉하지 않은 공기에 따른 구분 등을 해줘야 하기 때문에 풀이가 좀 복잡한 문제이다.

 우선 치즈 바깥 공기들에 대해서 이들이 모두 외부와 접촉해있다는 것을 표시해야 하기에, BFS 기반 함수로 이들을 채운다. 그 후에 전체 2차원 배열을 돌며, 녹는 치즈의 좌표를 큐에 저장한 후 이들을 한 번에 처리하여 특정 시간에 녹는 치즈들만의 값을 바꾼다. 그렇게 해당 좌표의 값을 바꾸고 나면 추가적으로 내부 공기가 외부 공기와 접촉될 수 있기 때문에, 추가적으로 주변 좌표에 대해 외부 접촉 공기를 확인하는 BFS 함수를 돌린다.

 이렇게 한 번의 과정을 while문으로 치즈가 모두 녹을때까지 반복하며, 그때마다 answer 값을 +1 해주면 이후 while 문이 끝나고 나서의 answer 값이 바로 답이 된다.

 

public class Main {
    static int[][] space;
    static int N, M, cheeseAmount = 0, answer = 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());

        space = new int[N][M];

        for (int i = 0; i < N; i++) {//격자 생성
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < M; j++) {
                space[i][j] = Integer.parseInt(st.nextToken());

                if (space[i][j] == 1) {
                    ++cheeseAmount;
                }
            }
        }

        paint(0, 0);//외부 공기 표시

        while (cheeseAmount != 0) {//모든 치즈가 녹을때까지
            Queue<Point> q = new LinkedList<>();

            for (int i = 1; i < N - 1; i++) {//각 위치에서 녹는 치즈 체크 후 큐에 저장
                for (int j = 1; j < M - 1; j++) {
                    int outCount = 0;
                    if (space[i][j] == 1) {
                        if (space[i - 1][j] == -1) {
                            ++outCount;
                        }
                        if (space[i + 1][j] == -1) {
                            ++outCount;
                        }
                        if (space[i][j - 1] == -1) {
                            ++outCount;
                        }
                        if (space[i][j + 1] == -1) {
                            ++outCount;
                        }

                        if (outCount >= 2) {
                            q.add(new Point(i, j));
                        }
                    }
                }
            }

            while (!q.isEmpty()) {//녹은 치즈 표시 후 추가 공기 표시
                Point p = q.poll();
                space[p.r][p.c] = -1;
                paint(p.r + 1, p.c);
                paint(p.r - 1, p.c);
                paint(p.r, p.c + 1);
                paint(p.r, p.c - 1);
                --cheeseAmount;
            }

            ++answer;
        }

        System.out.println(answer);
        return;
    }

    static void paint(int r, int c) {//bfs 기반 외부 공기 체크 함수
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c));

        while (!q.isEmpty()) {
            Point now = q.poll();

            if (now.r < 0 || N <= now.r || now.c < 0 || M <= now.c
                    || space[now.r][now.c] == 1 || space[now.r][now.c] == -1) {
                continue;
            }

            space[now.r][now.c] = -1;

            q.add(new Point(now.r + 1, now.c));
            q.add(new Point(now.r - 1, now.c));
            q.add(new Point(now.r, now.c + 1));
            q.add(new Point(now.r, now.c - 1));
        }
    }

    static class Point {//좌표 클래스
        int r, c;

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

결과