(JAVA) [BOJ]백준 2638번, 치즈

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

2638번: 치즈

 

2638, 치즈

📌 난이도 : Gold 3

📌 알고리즘 : DFS & BFS

 

이번 문제는 골드 3의 난이도지만 그렇게 어려운 문제는 아니였다. 외부공기와 외부공기가 유입되지 않는 구간만 잘 체크하면 된다! 문제를 잘 읽어보면 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다 는 말이 있다. 그렇다면 치즈가 아닌 공기가 유입될 수 있는 지역에서 DFS 로 모든 공기를 탐색하면 치즈가 있는 구간을 제외하고는 공기의 유입이 되지 않는 구역으로 정해진다. 이것을 유념해서 문제를 풀이해보자.

 

🧩 프로세스

📚 초기화 및 선언

: 다른 DFS & BFS 풀이들과 비슷하지만 여기서 int[][] Accessable 를 추가로 설정하여 유입되지 않는 구간을 분별한다.

 

📚 탐색

: 우선 공기가 유입되지 않는 구간을 구해야 한다. 이를 구하는 메서드 makeNotAccessArea() 를 생성해준다. 이는 위에서 설명한 것처럼 제일 빠른 공기의 좌표를 기반으로 BFS 진행하여 지역을 구한다.

public static void makeNotAccessArea() {
    Accessable = new boolean[N][M];

    Queue<Integer> Q = new LinkedList<>();
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            // 1회 탐색
            if(map[i][j] == 0) {
                Q.add(j);
                Q.add(i);
                break;
            }
        }
    }

    while(!Q.isEmpty()) {
        int x = Q.poll();
        int y = Q.poll();

        for(int k=0; k<4; k++) {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];

            if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
            if(Accessable[ny][nx]) continue;
            if(map[ny][nx] == 1) continue;

            Q.add(nx);
            Q.add(ny);
            Accessable[ny][nx] = true;
        }
    }
}

 

Accessble 의 값이 false이면 공기의 유입이 되지 않는 지역임을 의미한다. 그 후에 DFS 를 통해 치즈의 구역을 탐색하며 치즈를 지울 수 있는가 를 판단하는 check() 메서드를 설계한다. 예외조건을 통과하여 공기와 3면이 닿아있는 지를 판단한다.

// 공기와 3면 이상 닿아있는가
public static boolean check(int x, int y) {
    int CNT = 0;
    for(int k=0; k<4; k++) {
        int nx = x + dir[k][0];
        int ny = y + dir[k][1];

        if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
        if(map[ny][nx] == 1) continue;
        if(!Accessable[ny][nx]) continue;
        CNT++;
    }

    return CNT >= 2;
}

 

뽑은 데이터를 backet (stack) 과 참조하고 이후 로직을 진행하며 cnt 를 늘려가면 된다.

 

✅ 전체 코드

: Flag 를 체크하며 치즈를 줄여가다가 더 이상 지울 치즈가 없다면 루프를 종료하고 카운트를 출력하면 된다.

DFS & BFS 를 활용한 구현 느낌의 문제여서 재밌었다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] map, dir = {{1,0},{-1,0},{0,1},{0,-1}};
    static int N, M, ANS;
    static boolean[][] Accessable, visited;
    public static void main(String[] args) throws IOException {    
        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());
            }
        }

        int ANS = 0;
        while(true) {
            boolean deleted = false;
            visited = new boolean[N][M];

            // 유입되지 않는 지역을 선택
            // 공기인 구역에서 DFS 1회 호출 NotAccess = true
            // 이후에 치즈인 구역을 제외하면 유입되지 않는 지역!
            makeNotAccessArea();

            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(map[i][j] == 1 && !visited[i][j]) {
                        deleted = true;
                        DFS(j,i);
                    }
                }
            }

            if(!deleted) break;
            ANS++;
        }

        System.out.println(ANS);
    }

    public static void makeNotAccessArea() {
        Accessable = new boolean[N][M];

        Queue<Integer> Q = new LinkedList<>();
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                // 1회 탐색
                if(map[i][j] == 0) {
                    Q.add(j);
                    Q.add(i);
                    break;
                }
            }
        }

        while(!Q.isEmpty()) {
            int x = Q.poll();
            int y = Q.poll();

            for(int k=0; k<4; k++) {
                int nx = x + dir[k][0];
                int ny = y + dir[k][1];

                if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
                if(Accessable[ny][nx]) continue;
                if(map[ny][nx] == 1) continue;

                Q.add(nx);
                Q.add(ny);
                Accessable[ny][nx] = true;
            }
        }
    }

    public static void DFS(int x, int y) {
        visited[y][x] = true;

        if(check(x, y)) {
            map[y][x] = 0;
        }

        for(int k=0; k<4; k++) {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];

            if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
            if(map[ny][nx] == 0) continue;
            if(visited[ny][nx]) continue;
            
            DFS(nx, ny);
        }
    }

    // 공기와 3면 이상 닿아있는가
    public static boolean check(int x, int y) {
        int CNT = 0;
        for(int k=0; k<4; k++) {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];

            if(nx<0 || ny<0 || nx>=M || ny>=N) continue;
            if(map[ny][nx] == 1) continue;
            if(!Accessable[ny][nx]) continue;
            CNT++;
        }

        return CNT >= 2;
    }
}