61 삐약 : 백준 7576| 토마토 [바킹독 문제 풀이|BFS|JAVA]

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

 

 

package BKD_0x9_BFS;

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

public class BOJ_7576 {
    static int[] dx ={0,1,0,-1};
    static int[] dy ={1,0,-1,0};
    static int M;
    static int N;
    static int[][] box;
    static Queue<Pair> q = new LinkedList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        box = new int[N][M];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                box[i][j] = Integer.parseInt(st.nextToken());
                if(box[i][j]==1){
                    q.offer(new Pair(i,j,0));
                }
            }
        }

       bfs();
    }

    public static void bfs(){
        int days=0;
        while(!q.isEmpty()){
            Pair p =q.poll();
            days =p.days;
            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(nx>=0 && ny>=0 && nx<N && ny<M && box[nx][ny]==0){
                    q.offer(new Pair(nx,ny,days+1));
                    box[nx][ny]=1;

                }
            }
        }

        if(checkTomato()){
            System.out.println(days);
        }else System.out.println(-1);

    }

    static boolean checkTomato(){
        for(int[] arr : box){
            for(int tomato : arr){
                if(tomato==0) return false;
            }
        }
        return true;

    }
    static class Pair{
        int x;
        int y;
        int days;

        public Pair(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.days = d;
        }
    }

}

 

 

처음에는 q의 사이즈 만큼 반복문을 돌려서 끝내야 하나 생각을 했었는데 참고 블로그를 보고 내가 큐에 저장하는 클래스에 일수를 저장하는 방법을 택하였다.

생각해내는데 까지는 어려움이 없었으나 조금 더 생각 할 필요는 있다고 깨달았다 ㅋㅋㅋㅋㅋㅋㅋ

 

참고 url : 

https://cobi-98.tistory.com/38