백준7576 토마토

 

처음엔 dfs를 이용해 풀어보려고 했으나 실패했다.

 

bfs를 이용해 익은 토마토가 들어있는(1) 좌표를 q에 넣어주고,

상하좌우에 있는 토마토 중 안익은(0) 토마토가 들어있는 좌표가 있으면 익은 토마토 일수에서 1을 더해준다

즉 depth가 1 깊어질 때마다 1을 추가해 주는 것이다.

이렇게 하면 일수를 계산 가능하다.

 

그 후 countDay메서드를 통해

가장 깊은 depth를 cnt에 담아주고

depth는 1에서 시작했는데 일수는 0에서부터 시작했으니 날짜를 계산할 때는 1을 빼준다.

 

최종적으로

checkTomato메서드를 통해 안익은 토마토가 있으면 -1을 출력하고 

그렇지 않으면 모든 토마토가 있은것이므로 cnt를 출력한다.

 

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

public class Baek_7576 {
    static int[][] box;
    static int cnt;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int N;
    static int M;
    static Queue<int[]> 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];

        //1 익토 / 0안익토 / -1없토
        for (int i = 0; i < N; i++) {
            box[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (box[i][j] == 1) {
                    q.add(new int[]{i,j});
                }
            }
        }
        bfs();
        countDay();
        cnt = checkTomato()?cnt:-1;
        System.out.println(cnt);
    }

    static void bfs() {
        while (!q.isEmpty()){
            int[] t =q.poll();
            int x = t[0];
            int y = t[1];
            change(x,y);
        }
    }
//안익은 토마토가 있으면 false 출력
    static boolean checkTomato() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (box[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
    static int countDay(){
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cnt = Math.max(cnt,box[i][j]-1);
                }
            }
        return cnt;
    }

    //상하좌우중 0이 있으면 q에 넣고 depth+1
     static void change(int x, int y) {
            for (int i = 0; i < 4; i++) {
                int a = x + dx[i];
                int b = y + dy[i];
                if (a < 0 || b < 0 || a >= N || b >= M) {
                    continue;
                }
                if (box[a][b] == 0) {
                    box[a][b] = box[x][y] + 1;
                    q.add(new int[]{a, b});
                }
            }
        }
    }