[Java/자바] - 백준(BOJ) 2636번 : 치즈

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

2636번: 치즈

 

BFS를 이용해 가장자리 치즈를 줄여나가는 문제.

자바와 익숙해지기 위해 자바로 풀었다.

N * M 의 배열을 받아서 arr에 저장한다.

배열의 가장자리는 항상 치즈가 있지않으니 0,0을 Queue에 저장한다(LinkedList<> 이용)

이후 BFS를 돌려 0일 경우(치즈가 아님) Queue에 add해주고 visit을 1로 만들고

1일 경우(치즈임) visit을 1로 만들고 arr 값을 0으로 변경시킨다. (Queue add X)

이 과정을 치즈가 모두 사라질 때 까지 반복하며 time을 증가시키고 매번 반복을 시작할 때 남은 치즈 개수를 before에 저장한다.

모두 사라졌을때 time값과 before값을 출력한다.

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][m];
        int[] dy = {0, -1, 0, 1};
        int[] dx = {1, 0, -1, 0};
        int cheese = 0;
        int time = 0;
        int before = 0;
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j=0; j<m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) cheese++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        while (cheese > 0) {
            int[][] visit = new int[n][m];
            queue.add(0);
            queue.add(0);
            visit[0][0] = 1;
            before = cheese;
            time++;
            while (!queue.isEmpty()) {
                int y = queue.poll();
                int x = queue.poll();
                for (int i=0; i<4; i++) {
                    int yy = y + dy[i];
                    int xx = x + dx[i];
                    if (0 <= yy && yy < n && 0 <= xx && xx < m && visit[yy][xx] == 0) {
                        visit[yy][xx] = 1;
                        if (arr[yy][xx] == 0) {
                            queue.add(yy);
                            queue.add(xx);
                        }
                        else {
                            arr[yy][xx] = 0;
                            cheese--;
                        }
                    }
                }
            }
        }
        System.out.println(time + "\n" + before);
    }
}