[BOJ - JAVA] 2636 - 치즈 (시뮬레이션, BFS)

# 주소

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

2636번: 치즈

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
class Main{
    static int[][] arr;
    static boolean[][] visit;
    static int n, m;
    static int answer = 0;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        visit = new boolean[n][m];
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                arr[i][j] = scan.nextInt();
        int sum = 0;
        while(true){
            sum = 0;
            for(int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++){
                    if(arr[i][j] == 1)
                        sum++;
                }
            }
            list.add(sum);
            if(sum == 0)
                break;
            bfs();
            answer++;
        }
        Collections.sort(list);
        System.out.println(answer);
        System.out.println(list.get(1));
    }
    static void bfs(){
        queue = new LinkedList<>();
        visit = new boolean[n][m];
        queue.offer(new Point(0, 0));
        visit[0][0] = true;
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if(visit[nx][ny])
                    continue;
                if(arr[nx][ny] == 0){
                    queue.offer(new Point(nx, ny));
                    visit[nx][ny] = true;
                }
                if(arr[nx][ny] == 1){
                    arr[nx][ny] = 0;
                    visit[nx][ny] = true;
                }
            }
        }
    }
}

간단한 BFS문제였습니다.

공기와 맞닿아있는 부분의 치즈 값은 시간이 일정 시간 지날 때마다 녹아서 없어집니다.

문제에서 출력 기대값은 이 때 다 녹을 때 까지 걸리는 시간과 마지막으로 녹기 전에 남아 있던 치즈의 양을 출력을 요구합니다.

그렇담 bfs를 활용해야겠지요?

그러므로 arr와 visit, 큐를 활용합시다.

ArrayList는  치즈의 양을 저장할 자료구조로 사용할 것입니다.

살펴봅시다.

Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        visit = new boolean[n][m];
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                arr[i][j] = scan.nextInt();
        int sum = 0;

입력값은 이렇게 받아옵니다.

n과 m으로 입력받아 arr와 visit의 크기를 지정합니다.

그리고 arr에 입력값을 삽입하겠습니다.

while(true){
            sum = 0;
            for(int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++){
                    if(arr[i][j] == 1)
                        sum++;
                }
            }
            list.add(sum);
            if(sum == 0)
                break;
            bfs();
            answer++;
        }

이후 while문을 이용하여 탐색을 할텐데요.

우리가 탐색하는 경로는 치즈가 다 녹을 때 까지만이므로 만약 필드에 있는 치즈의 양이 0이면 break하여 while빠져나오게끔 세팅합니다.

그리고 sum 은 현재 필드의 치즈의 양으로, 만약 입력부터 치즈의 양이 0이면 바로 while문을 빠져나올 수가 있게됩니다.

또한 arr가 1일 때에 sum의 양을 증가시켜 새로 구한 치즈의 양을 아까 선언한 list에 담겠습니다.

그리고 bfs를 실행합니다.

static void bfs(){
        queue = new LinkedList<>();
        visit = new boolean[n][m];
        queue.offer(new Point(0, 0));
        visit[0][0] = true;
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dir[i][0];
                int ny = now.y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if(visit[nx][ny])
                    continue;
                if(arr[nx][ny] == 0){
                    queue.offer(new Point(nx, ny));
                    visit[nx][ny] = true;
                }
                if(arr[nx][ny] == 1){
                    arr[nx][ny] = 0;
                    visit[nx][ny] = true;
                }
            }
        }

bfs의 구조는 다음과 같습니다.

queue와 visit은 항상 초기화시켜주며 이 때 queue에는 시작점을 담겠습니다.

visit또한 true로 저장합니다.

그리고 while문에서 현재의 queue값을 now에 담고 4방향에 대해 탐색을 해야합니다.

여기서 중요한 사실은, 우리가 탐색하는 것은 치즈의 양이 아닙니다.

공기와 맞닿아있는 치즈를 탐색하여 해당 치즈를 모두 녹이고 0으로 바꾸어주어야합니다.

따라서 arr가 0이면 queue에 담고 visit도 true로 바꾸지만 arr가 1일 때에는 arr를 0으로, visit을 true로 바꾸되 queue에는 절대 삽입하면 안되겠습니다.

왜냐하면 치즈의 안으로 파고들기 때문이지요.

우리가 구하고 싶은 것은 공기와 맞닿아있는 치즈들이기 때문에 0과 맞닿은 1을 제거하는 것입니다.

이해가셨나요?

이 과정을 모두 마치면 시간이 1증가할테고 치즈도 녹아있겠지요.

이 과정을 계속 거치다보면 sum == 0이 될 때 break하여 while문을 빠져나올 것입니다.

그리고 아까 list에 담았던 치즈의 양들은 정렬을 하여야 합니다.

ArrayList에 담았던 치즈들을 모두 오름차순으로 정렬하겠습니다.

그런뒤 list의 1번째 값을 출력하면 정답이 됩니다. 

 

왜일까요? 

 

-> 치즈의 값들 중 두번째로 작은 값이 list.get(1)이고 가장 작은 0은 list.get(0)이기 때문입니다.

 

감사합니다.

이런 시뮬레이션 문제만 코테에 나오면 참 좋겠네요 ㅎ.