BOJ#2638 치즈

BOJ#2638 치즈

* 문제

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

* 풀이

가장자리에는 친절하게도 치즈가 존재하지 않으므로

가장자리에서 dfs 탐색을 하면 외부 공기 지역을 구별해낼 수 있습니다.

1. 외부 공기 탐색(dfs)

2. 모든 치즈에 대해 외부 공기 접촉 판단

3. 접촉 시 치즈 없애기

4. 1~3 반복....(치즈가 모두 없어질때까지)

주의할 점으로는...

치즈를 즉시 외부 공기로 바꾸면 주변 치즈에 영향을 주게 되어 정확한 답을 구할 수 없습니다.

개선할 점으로는...

step마다 dfs 탐색을 한번씩 수행하는 부분을 없앨 수 있겠습니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/c6b101df6246e4a5c45c00a905ca92dacf9864d2/BOJ%232638_Cheese/src/Main.java

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

/**
 * BOJ#2638 치즈
 * https://www.acmicpc.net/problem/2638
 */

public class Main {

    static int N, M;
    static int[][] map = new int[101][101];
    static boolean[][] visited = new boolean[101][101];

    static final int NONE = 0;
    static final int OUTER_AIR = 2;
    static final int CHEESE = 1;

    static final int[] dRow = {0, -1, 0, 1};
    static final int[] dCol = {-1, 0, 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());

        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 step = -1;
        boolean ret = false;
        while (!ret) {

            step++;

            init();
            dfs(0, 0);

            int cnt = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {

                    if (map[i][j] == CHEESE && checkCheese(i, j)) {

                        cnt++;
                    }
                }
            }
            // 종료
            if (cnt == 0) {

                ret = true;
                System.out.println(step);
            }
        }
    }

    static void dfs(int row, int col) {

        map[row][col] = OUTER_AIR;
        visited[row][col] = true;

        for (int i = 0; i < 4; i++) {

            int nextRow = row + dRow[i];
            int nextCol = col + dCol[i];

            if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) continue;
            if (visited[nextRow][nextCol]) continue;
            if (map[nextRow][nextCol] == CHEESE) continue;

            dfs(nextRow, nextCol);
        }
    }

    static void init() {

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {

                visited[i][j] = false;
            }
        }
    }

    static boolean checkCheese(int row, int col) {

        int cnt = 0;
        for (int i = 0; i < 4; i++) {

            int nextRow = row + dRow[i];
            int nextCol = col + dCol[i];

            if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) continue;
            if (map[nextRow][nextCol] == OUTER_AIR) cnt++;
        }

        if (cnt >= 2) {

            map[row][col] = NONE;
            return true;
        }
        return false;
    }
}