[BOJ_7576 | BFS]토마토

풀이

BFS를 이용하여 풀어야 하는 문제였다. 먼저 창고에 있는 토마토들을 쭉 스캔해서 큐에 넣는다.

큐는 FIFO(First - In - First - Out)의 성질을 가지는 자료구조이기 때문에

큐에 먼저 넣은 토마토들의 상하좌우의 좌표를 먼저 탐색할 수 있다.

창고에 있는 토마토들을 쭉 스캔해서 넣은 다음에는 !q.isEmpty()를 조건으로 while문을 이용한다.

큐에서 빼낸 좌표의 상하좌우의 좌표가 유효한지를 먼저 확인하고, (isValid)

그 좌표에 익지않은 토마토가 있다면 토마토를 익게 만들고,

원래의 토마토의 날짜에 1을 더해 익은 토마토의 좌표와 함께 큐에 다시 넣어주고 BFS를 반복한다.

즉, 큐에 들어가는 객체는 창고의 x좌표, y좌표, 그리고 경과일수가 들어가며, 

맨 처음 스캔할때의 경과일수는 0으로 시작하게 되고

큐에서 꺼낸 토마토의 상하좌우에 있는 익지 않은 토마토들을 익혀서 다시 큐에 넣어줄때는

경과일수 + 1을 더해서 넣어주면 된다.

while 루프를 빠져나왔을 때에 창고를 한번 더 스캔해서 0이 남아있다면, (익지 않은 토마토)

-1을 출력하면 되고, 그렇지 않다면 최대 경과일수를 출력하면 되는 문제이다.

소스 코드

import java.util.*;
import java.io.*;
public class BOJ_7576 {
 
    static int[][] map;
    static int n, m, cnt;
 
 
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        map = new int[n][m]; cnt = 0;
        // initialize
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){ map[i][j] = Integer.parseInt(st.nextToken()); }
        }
        BFS();
        boolean flag = false;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j] == 0) flag = true;
            }
        }
        if(flag) bw.write(-1+"\n");
        else bw.write(cnt+"\n");
        bw.flush();
        bw.close();
    }
 
    public static boolean isValid(int i, int j){
        if(i>=0 && i<n && j>=0 && j<m)return true;
        return false;
    }
 
    public static void BFS(){
        Queue<Coordinate> q = new LinkedList<Coordinate>();
        // insert data to queue
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){ if(map[i][j] == 1) q.offer(new Coordinate(i, j, 0)); }
        }
 
        while(!q.isEmpty()){
            int x = q.peek().x;
            int y = q.peek().y;
            int dayCnt = q.peek().dayCnt;
            q.poll();
 
            for(int i=-1;i<=1;i++){
                if(i!=0 && isValid(x+i, y) && map[x+i][y] == 0){
                    q.offer(new Coordinate(x+i, y, dayCnt+1));
                    map[x+i][y] = 1; cnt = dayCnt+1;
                }
            }
            for(int j=-1;j<=1;j++){
                if(j!=0 && isValid(x, y+j) && map[x][y+j] == 0){
                    q.offer(new Coordinate(x, y+j, dayCnt+1));
                    map[x][y+j] = 1; cnt = dayCnt+1;
                }
            }
        }
    }
 
    public static void print(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                System.out.print(map[i][j]+" ");
            }System.out.println();
        }System.out.println();
    }
}
class Coordinate{
    int x, y, dayCnt;
    Coordinate(int x, int y, int dayCnt){
        this.x = x;
        this.y = y;
        this.dayCnt = dayCnt;
    }
}