[골드3, BFS] 백준 2638 - 치즈 (자바)

Think

1. 문제를 딱 봤을때 엄청 어려워보이진 않았다. 내부공기, 외부공기 구분 하는 것만 신경써주면 될거같았다.
2. 가장자리는 무조건 치즈가 없으니, 0,0 BFS돌려서 외부공기로 넘버링하고, 치즈 탐색하면서 외부공기와 맞닿은 개수 체크한다음에, 녹은 치즈를 다시 외부공기로 넘버링 하는 방식으로 구현
3. 녹은 치즈를 바로 외부공기로 넘버링하면, 다음 탐색하는 치즈가 접촉하는 외부 공기의 수가 +1 되어버리니, 일단은 0으로 변환한다음에 이후 외부공기로 수정 

 

 

 

내 정답 코드

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

public class test {
    static int N, M, map[][],countCheeze;
    static boolean isVisited[][];
    static Queue<int[]> meltingCheezePosition = new ArrayDeque<>();
    static int[] dr = new int[]{0, 0, 1, -1};
    static int[] dc = new int[]{1, -1, 0, 0};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;


    public static void main(String[] args) throws IOException {
        init();

        process();

    }

    private static void process() {
        int second = 0;

        // 외부 공기를 -1로 넘버링
        numberingOutsideBFS(0, 0);

        // 치즈 개수가 0이 될때까지 반복
        while (countCheeze != 0) {

            // 치즈가 외부 공기와 접촉한 면이 2개 이상인지 체크 후, 해당 위치는 0으로 수정
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 1 && isContactedTwoOutside(i, j)) {
                        map[i][j] = 0;
                        meltingCheezePosition.add(new int[]{i,j});
                        countCheeze--;
                    }
                }
            }

            // 0으로 수정한 치즈를 -1로 수정하기
            int size = meltingCheezePosition.size();
            for (int i = 0; i < size; i++) {
                int[] p = meltingCheezePosition.poll();
                if(map[p[0]][p[1]] == 0){
                    numberingOutsideBFS(p[0], p[1]);
                }
            }

            second++;
        }

        System.out.println(second);
    }

    private static boolean isContactedTwoOutside(int r, int c) {
        int countOutside = 0;

        for (int i = 0; i < 4; i++) {
            int nextR = r + dr[i];
            int nextC = c + dc[i];

            if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M) continue;

            if(map[nextR][nextC] == -1){
                countOutside++;
            }
        }

        if(countOutside >= 2) return true;
        else return false;
    }

    private static void numberingOutsideBFS(int r, int c) {
        Queue<int[]> q = new ArrayDeque<>();

        isVisited = new boolean[N][M];
        isVisited[r][c] = true;
        q.add(new int[]{r, c});
        map[r][c] = -1;

        while (!q.isEmpty()) {
            int[] currentRC = q.poll();

            for (int i = 0; i < 4; i++) {
                int nextR = currentRC[0] + dr[i];
                int nextC = currentRC[1] + dc[i];

                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M || isVisited[nextR][nextC]) continue;

                if(map[nextR][nextC] == 0){
                    map[nextR][nextC] = -1;
                    q.add(new int[]{nextR,nextC});
                    isVisited[nextR][nextC] = true;
                }
            }
        }

    }

    private static void init() throws IOException {
        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)  countCheeze++;
            }
        }
    }
}

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

public class test {
    static int N, M, map[][],countCheeze;
    static boolean isVisited[][];
    static Queue<int[]> meltingCheezePosition = new ArrayDeque<>();
    static int[] dr = new int[]{0, 0, 1, -1};
    static int[] dc = new int[]{1, -1, 0, 0};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;


    public static void main(String[] args) throws IOException {
        init();

        process();

    }

    private static void process() {
        int second = 0;

        // 외부 공기를 -1로 넘버링
        numberingOutsideBFS(0, 0);

        // 치즈 개수가 0이 될때까지 반복
        while (countCheeze != 0) {

            // 치즈가 외부 공기와 접촉한 면이 2개 이상인지 체크 후, 해당 위치는 0으로 수정
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 1 && isContactedTwoOutside(i, j)) {
                        map[i][j] = 0;
                        meltingCheezePosition.add(new int[]{i,j});
                        countCheeze--;
                    }
                }
            }

            // 0으로 수정한 치즈를 -1로 수정하기
            int size = meltingCheezePosition.size();
            for (int i = 0; i < size; i++) {
                int[] p = meltingCheezePosition.poll();
                if(map[p[0]][p[1]] == 0){
                    numberingOutsideBFS(p[0], p[1]);
                }
            }

            second++;
        }

        System.out.println(second);
    }

    private static boolean isContactedTwoOutside(int r, int c) {
        int countOutside = 0;

        for (int i = 0; i < 4; i++) {
            int nextR = r + dr[i];
            int nextC = c + dc[i];

            if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M) continue;

            if(map[nextR][nextC] == -1){
                countOutside++;
            }
        }

        if(countOutside >= 2) return true;
        else return false;
    }

    private static void numberingOutsideBFS(int r, int c) {
        Queue<int[]> q = new ArrayDeque<>();

        isVisited = new boolean[N][M];
        isVisited[r][c] = true;
        q.add(new int[]{r, c});
        map[r][c] = -1;

        while (!q.isEmpty()) {
            int[] currentRC = q.poll();

            for (int i = 0; i < 4; i++) {
                int nextR = currentRC[0] + dr[i];
                int nextC = currentRC[1] + dc[i];

                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M || isVisited[nextR][nextC]) continue;

                if(map[nextR][nextC] == 0){
                    map[nextR][nextC] = -1;
                    q.add(new int[]{nextR,nextC});
                    isVisited[nextR][nextC] = true;
                }
            }
        }

    }

    private static void init() throws IOException {
        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)  countCheeze++;
            }
        }
    }
}