[Algo] 백준 2636 치즈 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/2636

메모리 : 15044KB

시간 : 144ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, M, cnt, turn;
    static int[][] map;
    static boolean[][] check;
    static int[][] vector = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        cnt = 0;
        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) {
                    map[i][j] = 999999; // 치즈를 999999로 처리
                    cnt++;
                }
            }
        }
        // dfs로 겉면만 돌면서 치즈를 녹인다
        turn = 0;
        int ans = cnt;
        while (cnt > 0) {
            check = new boolean[N][M];
            check[0][0] = true;
            int tmp = dfs(0, 0);
            if (tmp != 0) { //치즈가 다 녹기 전을 알아야하기 때문에
                ans = tmp;
            }
            turn++;
        }
        System.out.println(turn); //횟수
        System.out.println(ans); //치즈 수
    }

    private static int dfs(int r, int c) {
        for (int k = 0; k < 4; k++) {
            int x = r + vector[k][0];
            int y = c + vector[k][1];
            if (x < N && y < M && x >= 0 && y >= 0 && !check[x][y]) {
                check[x][y] = true;
                // 치즈면 녹아요
                if (map[x][y] == 999999) {
                    map[x][y] = turn + 1;
                    cnt--;
                }
                // 공기면 다시돌리기
                if (map[x][y] < turn + 1) {
                    dfs(x, y);
                }
            }
        }
        return cnt;
    }
}

풀이

그래프 탐색을 할 때 bfs를 이용하는 편이라 일단 bfs로 시도하려했으나, 이 경우에는 공기가 없는 빈칸에 대한 처리를 해줘야하기 때문에 겉만 순회할 수 있는 dfs로 풀었다.

1. 한 턴에 map을 한 번 돌아야 한다. > while로 cnt(개수)가 없어질 때 까지 반복
   1. 0,0은 무조건 공기이기 때문에 0,0부터 시작해 공기들을 탐색한다.
   2. 공기를 중심으로 사방탐색을 진행해 치즈가 있으면 녹인다
      • 치즈를 녹이는데 똑같이 0으로하면 탐색하다가 공기로 오인하고 들어갈 수 있다.
      • 그래서 원래 치즈를 엄청 큰 수 999999로 설정하고, 몇 번째 턴에 녹았는지 숫자로 표시해준다.
      • 공기인지 확인하고 그 부분을 탐색하는 과정을 진행할 때 "현재 턴보다 전 턴에 바뀐 공기일 때" 사방탐색을 해준다. map[x][y] < turn + 1
   3. 재귀스택이 다 돌아오면 한 턴 종료
2. 치즈가 모두 녹기 전 턴의 남아있는 치즈 수를 알고싶다.
   1. 따라서 입력을 받을 때 전체 치즈의 수를 알고,
   2. 치즈를 공기로 바꿀 때 하나씩 감소시켜준 다음
   3. 치즈가 다 녹은 경우(즉 마지막 턴)의 전 경우를 ans에 저장한다.
   4. 첫 턴에 치즈가 다 녹을 수 있기 때문에 ans의 초기값을 cnt로 정해놓는다.

몸이 아파서 집중해서 한 번에 풀지 못했다ㅜ 하지만 귀여운 문제였다.