백준 2638, 치즈(java)

문제 설명

치즈(2636) 문제에서 공기와 면을 두 개 이상 맞닿고 있는 치즈만 녹이는 것이다.

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

2638번: 치즈

문제 풀이

해당 문제의 풀이를 보기에 앞에 골드 4 레벨의 치즈 문제(백준, 2636)를 한 번 풀고 오는 것을 추천한다.

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

2636번: 치즈

https://jiwonna52.tistory.com/96

백준 2636, 치즈(java)

 

이번 문제는 공기와 접한 면이 2개 이상일 때만 치즈가 녹는 경우이다. 그러므로 공기를 기준으로 너비 우선 탐색을 하되 치즈를 만나면 해당 치즈가 공기와 맞닿는 면이 존재한다는 의미로 count 배열에 값을 하나 올려준다. 그리고 치즈가 녹는 기준은 공기와 맞닿은 면이 2개 이상일 때다.

 

위의 부분만 구현해준다면 쉽게 문제를 풀 수 있을 것이다.

import java.util.*;
import java.io.*;

class Pair {
    int r;
    int c;

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

public class Main {
    public static int n, m;
    public static int[][] map;
    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};

    // 빈칸을 기준으로 처음 만나는 치즈가 외벽이다.
    public static void bfs() {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(0, 0));
        boolean[][] visit = new boolean[n][m];
        int[][] count = new int[n][m];

        while(!queue.isEmpty()) {
            Pair current = queue.poll();
            int cR = current.r;
            int cC = current.c;

            for (int i=0; i<4; i++) {
                int nR = cR + dR[i];
                int nC = cC + dC[i];

                if (nR >= 0 && nR < n && nC >= 0 && nC < m) {
                    if (!visit[nR][nC]) {
                        if (map[nR][nC] == 0) {
                            visit[nR][nC] = true;
                            queue.add(new Pair(nR, nC));
                        } else {
                            count[nR][nC] += 1;
                        }
                    }
                }
            }
        }

        melt(count);
    }

    public static void melt(int[][] count) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (count[i][j] >= 2) {
                    map[i][j] = 0;
                }
            }
        }
    }

    public static boolean checkIfFinish() {
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (map[i][j] == 1) {
                    return false;
                }
            }
        }

        return true;
    }


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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        int answer = 0;

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

        while(!checkIfFinish()) {
            bfs();
            answer++;
        }

        System.out.println(answer);
    }

}