[ baekjoon ] 치즈 2636번 ( Java )

문제

백준 2636 치즈 풀이 ( 자바 )

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

2636번: 치즈

 

풀이

치즈의 개수가 0이 될 때까지 bfs를 돌린다.

마지막에 0개가 된기전 cnt값을 저장하기 때문에 cnt를 출력하면 마지막에 남은 치즈 값이다.

그리고 bfs를 돌릴 때마다 visited를 초기화 해줘야 한다.

import java.util.*;
import java.io.*;

public class _2636 {

   static int n, m, cheese;
    static int[][] arr;
    static int[][] visited;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {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());

        arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int val = Integer.parseInt(st.nextToken());
               arr[i][j] = val;
               if(val == 1) {
                   cheese += 1;
               }
            }
        }
        int time = 0;
        int cnt = 0;

        while (cheese != 0) {
            time += 1;
            cnt = cheese;
            bfs();
        }
        
        System.out.println(time);
        System.out.println(cnt);
    }

    public static void bfs() {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));

        visited = new int[n][m];

        while(!q.isEmpty()) {
            Point now = q.poll();
            int cx = now.x;
            int cy = now.y;
            for(int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny] == 1) {
                    continue;
                }

                if(arr[nx][ny] == 1) {
                    cheese -= 1;
                    arr[nx][ny] = 0;
                }else if(arr[nx][ny] == 0) {
                    q.add(new Point(nx, ny));
                }
                visited[nx][ny] = 1;
                
            }
        }
    }
}

class Point {
    int x;
    int y;

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