[JAVA] 백준 7576번- 토마토

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

7576번: 토마토

 

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 Main {
    static int n, m;
    static int[][] arr;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int day;
    static Queue<Point> queue = new LinkedList<>();

    static class Point {
        int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void bfs() {
        while (!queue.isEmpty()) {
            Point p = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || arr[nx][ny]==-1) continue;

                if(arr[nx][ny] == 0){ // 아직 익지 않은 토마토라면
                    arr[nx][ny] = arr[p.x][p.y]+1; // 이전 토마토까지 익는데 걸린 날짜 + 1
                    queue.add(new Point(nx,ny));
                }
            }
        }
    }

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

        arr = new int[m][n];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 1) queue.offer(new Point(i, j)); // 익은 토마토면 큐에 넣음
            }
        }

        bfs();

        boolean flag = true;
        int day = Integer.MIN_VALUE;
        loop:
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j] == 0) { // bfs를 돌고도 익지 않은 토마토가 남아있다면
                    flag = false;
                    break loop;
                }
                else day = Math.max(day, arr[i][j]); // 모든 토마토가 익는데 걸린 시간은 배열 값 중에 가장 큰 값
            }
        }
        if(!flag) System.out.println(-1);
        else System.out.println(day-1); // 첫 시작 값이 1이였으므로
    }
}

 

 

최소 날짜를 구해야 하므로 bfs로 푼다. 

이 문제에서 포인트는 익은 토마토가 여러개 있을 때 같이 시작하여 그 주위 토마토들로 퍼져 나간다는 것인데,

그렇기 때문에 일단 익은 토마토의 좌표를 입력받아 큐에 다 집어넣고 bfs를 시작해야 한다.