[BOJ] 2636 - 치즈

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/2636

2636번: 치즈

난이도: 골드 5

사용언어: JAVA

 

풀이

이 문제는 BFS를 이용하여 해결할 수 있습니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/63

[BOJ] 2178 - 미로 탐색

 

저는 다음과 같은 로직으로 문제를 해결했습니다.

 

1. BFS를 통해 해당 시점의 치즈(1)를 찾아낸다.

2. BFS를 도는 동안 1(가장자리)을 발견하면 큐에 집어넣는다.

3. BFS가 끝난 뒤, 큐에서 가장자리를 빼면서 녹은 것으로 처리해준다.

 

이 로직을 반복문을 돌며 계속 반복시켰습니다. 이 세 단계를 다 거치면 문제에서의 한 시간 동안 일어나는 일을 구현할 수 있습니다.

 

이를 남은 1이 없을 때까지 반복해주면 됩니다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static int N, M;
    static int l = 0;
    static class position { // 큐에 위치 정보를 넣기 위해 선언한 class
        int x;
        int y;
    }
    static int cnt = 0;
    static int[][] d = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}}; // BFS에 활용할 방향 4가지
    static Queue<position> q = new LinkedList<>(); // BFS에 사용하는 큐
    static Queue<position> q2 = new LinkedList<>(); // 가장자리 부분을 저장할 큐
 
    public static void bfs(int x, int y, int arr[][]) {
        int i;
        for (i = 0; i < 4; i++) {
            position p = new position();
            if (x + d[i][0] >= 0 && x + d[i][0] < N && y + d[i][1] >= 0 && y + d[i][1] < M) { // 배열의 크기를 벗어나지 않도록 검사
                if(arr[x + d[i][0]][y + d[i][1]] == l || arr[x + d[i][0]][y + d[i][1]] == 0) { // 해당 칸이 치즈가 아니면,
                    p.x = x + d[i][0];
                    p.y = y + d[i][1];
                    q.add(p); // BFS를 위한 큐에 삽입
                    arr[p.x][p.y] = l - 1; // 확인한 곳인지를 마킹하기 위해 l이라는 변수 사용. 반복문을 돌 때마다 1씩 감소시켜 반복문을 몇 번 돌았는지 카운트 용도로도 사용됨
                }
                if(arr[x + d[i][0]][y + d[i][1]] == 1) { // 치즈의 가장자리가 나오면
                    arr[x + d[i][0]][y + d[i][1]] = 2; // 이미 확인한 곳이라는 뜻으로 2로 마킹
                    p.x = x + d[i][0];
                    p.y = y + d[i][1];
                    q2.add(p); // 가장자리를 위한 큐에 삽입
                    cnt++; // 가장자리의 개수 카운팅
                }
            }
        }
    }
 
 
    public static void main(String[] args) throws IOException {
        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());
 
        int i, j, k=0;
        int[][] arr = new int[N][M];
        int[] result = new int[1000];
        for (i = 0; i < N; i++) {
            s = br.readLine();
            st = new StringTokenizer(s);
            for (j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        position p = new position();
 
        while (true) {
            p.x = 0; // (0,0)부터 BFS 시작
            p.y = 0;
            q.add(p);
 
            while(true) {
                if(q.size()==0) // 종료 조건: 더 이상 확인할 0이 없음 (끝까지 다 확인함)
                    break;
                k = q.size();
                for (i = 0; i < k; i++) { // 큐에서 빼내어 BFS 수행
                    p = q.remove();
                    arr[p.x][p.y] = l -1;
                    bfs(p.x, p.y, arr);
                }
            }
 
            if(q2.size()==0) // 더이상 가장자리(1)가 남아있지 않다면 반복문 종료
                break;
 
            while(true){
                if(q2.size()==0)
                    break;
                p = q2.remove();
                arr[p.x][p.y] = l-1;
           } // 가장자리들을 모두 큐에서 빼내어 녹은것으로 처리. (다른 바닥과 같은 값으로 수정)
            result[l*-1] = cnt; // 가장자리의 개수값을 저장
            l--;
            cnt = 0;
 
        }
        l = l * -1;
        System.out.println(l); // 위에서도 언급했듯이 l 변수는 반복문을 몇번 돌았는지도 카운팅
        System.out.println(result[l-1]); // 가장자리의 개수들을 저장했던 result 배열에서 직전 반복문의 cnt를 찾아옴
    }
}