[백준 / Java] 2638 치즈

문제 정보

• 난이도: 골드 3
• 태그: 구현, 그래프, 시뮬레이션, DFS, BFS

접근

처음에 떠올린 풀이는 (먼저 말해두지만 틀린 풀이입니다.)
1. 이중포문으로 칸 하나하나 검사한다.
2. 만약 치즈인 칸을 만나면 그 칸의 상하좌우를 보고 뚫려있는 곳(0)이면 그 칸에서 DFS를 시작한다.
3. DFS를 돌리다가 맵 바깥에 닿게 되면 바깥 공기이므로, 그렇게 바깥공기와 2번 닿으면 그 칸을 ArrayList에 넣어둔다.
4. 이중포문을 빠져나오면 ArrayList 담긴 좌표의 map 값을 0으로 바꾼다. (치즈 녹이기)
5. 위 과정을 치즈가 모두 없어질 때까지 반복한다.

라는 엄청난 말도 안되는 풀이를 생각했었다.
이렇게 풀면, map이 NxM 사이즈이고, 치즈의 개수가 K개 일때,

• DFS 한번 돌릴 때: O(NM)
• 와일문 한번 돌때마다 치즈의 상하좌우 다 확인: O(4K)
• while문 도는 횟수: 최대로 잡았을때 O(K)

O(K^2NM)인 엄청난 시간 복잡도로 풀수 있다...
이 풀이로 풀면 메모리 초과가 났었다.

풀이

제대로 된 풀이는 다음과 같다.

1. (1, 1)에서 DFS를 돌린다 (BFS도 상관없다.)
2. DFS 중에는 치즈가 없는 칸만 방문을 한다. (즉 map의 값이 0인 칸만 방문)
3. 만약 현재 칸(치즈 없는 칸)에서 상하좌우를 보았을 때 치즈가 있다면 그 치즈는 바깥공기와 닿은 것이 된다. 따라서 그 치즈 칸의 수를 1 증가 시킨다. 그리고 치즈 칸은 DFS를 돌지 않고 continue한다.
4. DFS를 빠져나온 후, 이중포문을 돌면서 map 배열을 검사한다. map의 값이 3이상이라면 0으로 바꾸어주고(치즈 녹이기), 2라면 1로 되돌려 준다. 값이 3 이상일 때 녹이는 이유는, 치즈는 처음에 1로 표시가 되고 바깥 공기와 닿을 때마다 1씩 증가하게 된다. 따라서 값이 3이상이면 바깥공기와 2면 이상 닿은 치즈라는 것이므로 녹인다.
5. 이를 모든 치즈가 녹을 때까지 while문으로 반복한다.
   

민트색으로 표시된 부분만 DFS에서 방문하게 됨. 치즈 부분은 DFS로 방문하지 않기 때문에, 바깥공기가 아닌 빈공간도 방문할 수 없게 된다.
민트색 부분을 방문하고 상하좌우를 봤을 때, 치즈가 있으면 1 증가시키고 dfs 후에 3 이상의 값을 가지고 있는 치즈를 녹인다.

바깥 공기와 닿은 치즈를 검사할 때 DFS, BFS 중 무엇을 써도 상관없다.

코드는 다음과 같다.

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

class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    // 상하좌우 확인 용 dy, dx 배열
    static int dy[] = {1, -1, 0, 0};
    static int dx[] = {0, 0, -1, 1};
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];

        int count = 0; // 치즈의 수
        // 격자 입력 받는 부분
        for(int i=1; i<=N; ++i) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=M; ++j) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1) ++count;
            }
        }
        //
        
        
        int turn = 0;
        while(count > 0) { // count(치즈 수)가 0 될때까지 반복
       
            turn++;

             // visited 초기화
            for(int i=0; i<=N; ++i) {
                for(int j=0; j<=M; ++j){
                    visited[i][j] = false;

                    if(map[i][j] >=2) map[i][j] = 1;
                }
            }

            dfs(1, 1); // (1, 1) 칸은 치즈가 없음이 보장된다. 
            // dfs에서 빠져나오면 맵을 쭉 검사한다.
            for(int i=1; i<=N; ++i) {
                for(int j=1; j<=M; ++j) {
                    if(map[i][j] >= 3) { // 3이상이면 바깥공기와 2면 이상 닿은 것임
                        map[i][j] = 0;
                        --count; // 치즈 수 감소
                    }
                }
            }

        }

        bw.write(turn + "\n"); bw.flush();

    }

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

        for(int i=0; i<4; ++i) {
            int ny = y + dy[i], nx = x + dx[i];
            if(ny > N || ny <= 0 || nx <= 0 || nx > M) continue;

            if(map[ny][nx] >= 1) {
                map[ny][nx] += 1;
                continue;
            }
            if(visited[ny][nx]) continue;

            dfs(ny, nx);

        }

    }
}

자체 피드백

• 위에 static int 로 N, M을 선언해놓고, 메인 메소드 안에서 int N, M으로 지역 변수를 선언하고 거기다가 입력을 받아서 dfs를 돌릴 때 if(ny > N || ny <= 0 || nx <= 0 || nx > M) continue;에서 다 continue 돼서 while이 무한 루프를 도는 실수를 했었다. 이런 실수 안하도록 신경쓰자