백준 2638번 : 치즈 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

치즈 골드 3

 

📖 문제

 

외부 공기를 기준으로 BFS 탐색하여 

치즈와 맞닿으면 카운팅해준다. 

 

그런데 다른 풀이를 보고 했는데 치즈가 가장자리 (0,0)에서 시작할 수도 있지 않나 싶은데

0,0 부터 외부 공기 찾는 로직이 있어도 다 통과해서 

치즈가 가장자리에는 위치하지 않나보다.

 

나는 치즈의 처음 만나는 지점과 마지막 지점을 구하고, 

안쪽 방향을 제외한 3방향을 탐색해서 공기외부 좌표를 구한다음

BFS 탐색을 하여 공기 접촉 탐색을 했다. 공기를 2번 이상 접촉하면

그 지점을 공기로 만들면 된다. 

 

 

7 7
1 1 1 0 0 0 0
1 0 1 1 0 0 0
1 0 1 0 1 0 0
0 1 0 1 0 1 0
0 0 1 0 1 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0


//answer 5

 

 

 

---

🔅 문제 풀이

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

public class Main {


    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};
    static int[][] graph;

    static Queue<int[]> externalAirQueue = new LinkedList<>();
    static int[][] contactCountCheck;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        graph = new int[n][m];


        int[] firstCheese = {-1, -1};
        int[] lastCheese = {-1, -1};

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 처음 만나는 치즈 위치를 저장
                if (graph[i][j] == 1) {
                    firstCheese = new int[]{i, j};
                    break;
                }
            }
            if (firstCheese[0] != -1) break;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                // 마지막 치즈 위치를 저장
                if (graph[i][j] == 1) {
                    lastCheese = new int[]{i, j};
                    break;
                }
            }
            if (lastCheese[0] != -1) break;
        }

        // 치즈의 외부 공간 좌표를 모두 얻는다.
        getExternalSpace(firstCheese, n, m, true);
        getExternalSpace(lastCheese, n, m,false);


        int time = 0;
        while (true) {
            // 모든 치즈가 삭제되었다면 멈춤
            if (bfs(n, m)) break;

            // 시간이 지나고 상한 치즈를 삭제
            time++;
            removeCheese(n,m);
        }


        bw.write(time + "");
        bw.flush();
        bw.close();
    }

    static List<int[]> externalSpace = new ArrayList<>();

    private static void getExternalSpace(int[] cheesePos, int n, int m, boolean isFirst) {
        // 처음만난 치즈와 접촉하는 4방향중 외부의 한 좌표를 구함
        for (int i = 0; i < 4; i++) {
            if (isFirst && i == 0) continue;
            else if (!isFirst && i== 1) continue;

            int nextR = cheesePos[0] + dy[i];
            int nextC = cheesePos[1] + dx[i];
            if (nextR <0 || nextR >= n || nextC < 0 || nextC >= m || graph[nextR][nextC] == 1) continue;
            externalSpace.add(new int[]{nextR, nextC});
        }
    }

    // 상한 치즈 삭제
    private static void removeCheese(int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (contactCountCheck[i][j] >= 2) {
                    graph[i][j] = 0;
                }
            }
        }
    }

    // 외부 접촉 탐색
    private static boolean bfs(int n, int m) {
        contactCountCheck = new int[n][m];
        boolean allRemovedCheese = true;

        // 외부로 확정된 위치들을 큐에 넣는다.
        for (int[] pos : externalSpace) {
            externalAirQueue.add(pos);
            contactCountCheck[pos[0]][pos[1]] = -1;
        }

        while (!externalAirQueue.isEmpty()) {
            int[] current = externalAirQueue.poll();

            // 4방향으로 이동
            for (int i = 0; i < 4; i++) {
                int nextR = current[0] + dy[i];
                int nextC = current[1] + dx[i];

                if (nextR < 0 || nextR >= n || nextC < 0 || nextC >= m) {
                    continue;
                }

                // 빈 공간이고 아직 방문하지 않았다면 방문하고 큐에 추가
                if (graph[nextR][nextC] == 0 && contactCountCheck[nextR][nextC] == 0) {
                    contactCountCheck[nextR][nextC] = -1;
                    externalAirQueue.add(new int[]{nextR, nextC});

                    // 치즈 공간이라면 접촉 횟수를 + 1
                } else if (graph[nextR][nextC] == 1) {
                    contactCountCheck[nextR][nextC]++;
                    allRemovedCheese = false;
                }
            }
        }

        return allRemovedCheese;
    }

}

 

 

❗ 오답노트 / 필요한 지식

1.