백준 2636 (치즈) java

문제

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

2636번: 치즈

 

import java.util.*;
import java.io.*;
import java.awt.Point;
public class Main {
    static int num=0;
    static int n = 0;
    static int m = 0;
    static int[][] board = new int[101][101];
    static int[][] visit =  new int[101][101];
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static Queue<pair> q = new LinkedList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int i= 1;i<=n;i++)
        {
            st = new StringTokenizer(bf.readLine()," ");
            for(int j=1;j<=m;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j]==1)
                    num=num+1;

                if(i==1||i==n||j==1||j==m)
                    q.add(new pair(i,j));
            }
        }
        int hour=0;
        while(true)
        {
            if(num==0)
                break;

            int result =  bfs();
            hour=hour+1;

            if(num-result==0)
            {
                break;
            }
            num = num -result;
        }
        System.out.println(hour);
        System.out.println(num);

        bf.close();
    }

    static int bfs() {
        int result = 0;
       Queue<pair> sub =new LinkedList<>(); // 다음 탐색을 위한 큐
       while(!q.isEmpty())
       {
           pair cur = q.poll();
           for(int i=0;i<4;i++)
           {
               int nx = cur.x+ dx[i];
               int ny = cur.y + dy[i];

               if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
               {
                   if(visit[nx][ny]==0&&board[nx][ny]==0)
                   {
                       visit[nx][ny]=1;
                       q.add(new pair(nx,ny));
                   }
                   else if(visit[nx][ny]==0&&board[nx][ny]==1)
                   {
                       visit[nx][ny]=1;
                       board[nx][ny]=0;
                       result = result +1;
                       sub.add(new pair(nx,ny)); // 치즈가 녹은 부분을 기준으로 다음 탐색 진행
                   }
               }
           }
       }
       q = new LinkedList<>(sub);
       return result;
    }

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

 

 

입력을 받는 과정에 있어서 '가장자리'의 좌표값을 큐에 집어넣는다. 그 이유는 '바깥'을 기준으로 탐색하기 위해서이다.

 

 

bfs() 함수내에서 주요 로직이다. '바깥'일 경우에는 큐에 추가하여 탐색을 지속하고 '치즈의 부분'일 경우에는 방문처리를 하고 녹인다. 그리고 sub라는 보조 큐에 추가해주는데 그 이유는 다음 탐색을 진행하는 과정에서 sub안에 있는 값들을 기준으로 탐색하기 위해서이다.