[백준/2636] 치즈 - JAVA

📌 문제

알고리즘 분류 : 그래프
난이도 : 골드4
출처 : 백준 - 치즈

🦧 문제 풀이 접근

0,0좌표랑 붙어있는 0을 DFS로 모두 찾는 과정을 반복한다.
그 과정에서 0이랑 인접해있는 1을 모두 0으로 바꾼다.
해당 과정을 반복하면서 모든 1이 없어진 순간을 체크한다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    static boolean cheese[][];
    static int cheeseCnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        cheese = new boolean[N][M];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                if(st.nextToken().equals("0"))
                    cheese[i][j] = false;
                else {
                    cheese[i][j] = true;
                    cheeseCnt++;
                }

            }
        }
        int cnt = 0, lastCheeseCnt=0;
        while(cheeseCnt>0) {
            boolean check[][] = new boolean[N][M];
            lastCheeseCnt = cheeseCnt;
            cnt++;
            DFS(0,0,check);
        }
        System.out.println(cnt+"\n"+lastCheeseCnt);
    }
    static void DFS(int i, int j, boolean[][] check) {
        int[] di = {0,1,0,-1}, dj = {1,0,-1,0};
        for(int k=0;k<4;k++) {
            int ci = i+di[k], cj = j+dj[k];
            if(ci<0 || cheese.length-1<ci || cj<0 || cheese[0].length-1<cj) {
                continue;
            }
            if(!cheese[ci][cj] && !check[ci][cj]) {
                check[ci][cj]=true;
                DFS(ci,cj,check);
            }
            else if(cheese[ci][cj] && !check[ci][cj]) {
                cheese[ci][cj] = false;
                check[ci][cj]=true;
                cheeseCnt--;
            }
        }
    }
}

🥇 결과

🎓 느낀점

기본 DFS문제에서 몇가지 조건문을 추가해야해서 머리를 써야한다. 특히 몇몇 변수를 전역변수로 선언해서 쉽게 풀 수 있었다.