[알고리즘] 백준 2636 치즈 - JAVA

www.acmicpc.net/problem/2636

2636번: 치즈

문제설명

치즈의 모서리(입력 배열에서 0과 맞닿아 있는 부분중에서 바깥부분)이 시간마다 녹는다.

 

이 때 치즈가 다 녹는 시간과 다 녹기 직전 시간의 치즈의 개수를 구하는 문제이다.

 

해결방법

처음에는 1인 부분부터 BFS를 돌려서 0과 맞닿아있으면 모서리라고 생각해 그것을 녹여간다는 방향으로 생각했다.

 

근데 이렇게 하면 치즈 내부에 형성된 모서리를 찾을 수 없다.

 

그렇기 때문에 무조건 치즈가 존재하지 않는 (0,0)부터 치즈가 없는 부분을 BFS를 통해 탐색한다.

 

탐색 과정에서 1을 만나게 되면 모서리로 판단한다.

 

이렇게 탐색하면 치즈 내부를 절대 탐색할 수 없으므로 안쪽의 모서리에 대해 생각하지 않아도 된다.

 

다만 주의해야할 점은 1시간만에 모든 치즈가 다 녹는 예외를 처리해줘야한다.

 

이것을 위해 첫번째 BFS가 돌아가기전에 치즈의 개수를 세주었다.

 

구현 내용에 대한 설명은 주석으로 대체한다.

 

소스코드

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

class Main {

    static int n;
    static int m;

    static int[][] map;
    static boolean[][] visited;

    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};
    static List<Integer> list = new ArrayList<>(); // 치즈 개수가 들어갈 list

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");

            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // input end

        boolean flag = true; // 모든 치즈가 녹아 없어지면 flag는 false가 된다.
        int time = 0; // 시간
        int firstCount = getCount(); // 초기상태 치즈의 개수

        while (flag) {
            time++;

            bfs(new Location(0, 0));

            for (int i = 0; i < n; i++)
                Arrays.fill(visited[i], false); // 다음 시간에 치즈를 녹이기 위해 visited 배열 전부 false를 넣어줌

            int count = getCount();

            if (count == 0)
                flag = false;
            else
                list.add(count);
        }

        System.out.println(time);

        if (list.size() > 0) // 치즈가 전부 녹는데 2시간 이상인 경우
            System.out.println(list.get(list.size() - 1));
        else // 1시간만에 치즈가 다 녹는 경우 혹은 치즈가 하나도 없을 때.
            System.out.println(firstCount);

    }

    // 0.0 부터 돌려서 1을 만나면 2로

    static void bfs(Location location) {

        Queue<Location> queue = new LinkedList<>();
        queue.add(location);
        visited[location.x][location.y] = true;

        while (!queue.isEmpty()) {
            Location current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (!visited[nx][ny]) {
                        if (map[nx][ny] == 1) { // 치즈의 모서리를 일단 2로 변경한다.
                            map[nx][ny] = 2;
                            visited[nx][ny] = true;
                        }
                        if (map[nx][ny] == 0) {
                            visited[nx][ny] = true;
                            queue.add(new Location(nx, ny));
                        }
                    }
                }
            }
        }

        removeCheese(); // 배열의 값이 2면 치즈의 모서리이므로 0으로 바꾸어 녹여버림
    }

    static void removeCheese() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 2)
                    map[i][j] = 0;
            }
        }
    }

    static int getCount() {

        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1) {
                    count++;
                }
            }
        }

        return count;
    }

    static class Location {
        int x;
        int y;

        public Location(int x, int y) {
            this.x= x;
            this.y = y;
        }
    }
}