[백준]2636: 치즈 - JAVA

[백준]2636: 치즈

www.acmicpc.net/problem/2636

2636번: 치즈

풀이

BFS 탐색 알고리즘을 사용하여 문제를 풀었다.

 

우선, 현재 치즈의 개수를 세어 준 다음 치즈 개수가 0이 아닐때까지 BFS 탐색을 하며 치즈의 개수를 줄여나갔다. 탐색은 0,0부터 시작하여 치즈를 만나면 해당 치즈를 없애주고, 치즈가 아니라면 큐에 넣어 근처에 있는 치즈를 탐색하도록 하였다.

 

코드

import java.util.*;
 
public class Main {
    
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static int[][] board;
    static int n, m;
    static int cheese;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        board = new int[n][m];
        cheese = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] = scan.nextInt();
                if(board[i][j] == 1) cheese++;
            }
        }
        
        int cheeseCount = 0;
        int time = 0;
        while(cheese != 0) {
            cheeseCount = cheese;
            time++;
            visited = new boolean[n][m];
            bfs();
        }
        System.out.println(time);
        System.out.println(cheeseCount);
    }
    
    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {0, 0});
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            int[] current = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == false) {
                    visited[nx][ny] = true;
                    if(board[nx][ny] == 0) {
                        q.offer(new int[] {nx, ny});
                    } else {
                        cheese--;
                        board[nx][ny] = 0;
                    }
                }
            }
        }
    }
}