[Java] 백준 7576 토마토

 

 

문제

M x N 크기의 상자와 각 칸에 들어있는 토마토의 상태가 주어진다. (1: 익은 토마토, 0: 안익은 토마토, -1: 토마토 없음)

익은 토마토는 인접한 안익은 토마토를 익게만든다고 할 때, 토마토가 모두 익을 때까지 최소 날짜를 출력해라.

모두 익을 수 없는 경우엔 -1, 이미 모두 익어있는 경우엔 0을 출력한다.

(2 <= M,N <= 1,000)

 

 

풀이

맨 처음 주어지는 익은 토마토의 개수가 1개라는 보장이 없다. 

이 때 for문을 돌며 익은 토마토를 발견한 순서대로 즉시 bfs로 탐색하게 된다면 최소날짜를 구할 수 없다. (예제 입력 3의 경우)

따라서 box배열이 주어질 때 미리 익은 토마토들의 위치를 queue에 모두 삽입한 다음 탐색해야 한다.

 

 

코드

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 b7576 {
    static int UNRIPE = 0, RIPE = 1;
    static int M, N, unripe_cnt;
    static int[][] box;
    static Queue<Point> queue;

    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());
        unripe_cnt = 0; // 안익은 토마토 개수

        box = new int[N][M];
        queue = new LinkedList<>();
        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] == UNRIPE) unripe_cnt++;
                else if (box[i][j] == RIPE) queue.add(new Point(i, j, 0)); // queue 세팅
            }
        }

        if (unripe_cnt == 0) { // 안익은 토마토가 없는 경우 
            System.out.println(0);
            return;
        }

        int result = bfs();
        if (unripe_cnt > 0) // 토마토가 다 익을 수 없는 경우
            System.out.println(-1);
        else
            System.out.println(result);
    }

    static int bfs() {
        int maxDay = 0;
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            Point curr = queue.poll();
            maxDay = curr.days + 1;

            for (int k = 0; k < 4; k++) {
                int nx = curr.x + dx[k];
                int ny = curr.y + dy[k];
                if (isRange(nx, ny) && box[nx][ny] == UNRIPE) { // 인접한 토마토가 안익은 토마토라면
                    queue.add(new Point(nx, ny, maxDay));
                    box[nx][ny] = maxDay;
                    unripe_cnt--;
                }
            }

        }// end of while

        return maxDay - 1;
    }

    static boolean isRange(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= M)
            return false;
        return true;
    }

    static class Point {
        int x, y, days;

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

 

 

채점결과