[백준 7576, JAVA] - 토마토

문제

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

풀이

토마토가 모두 익는 최소 일수를 구해야 하는 문제여서 BFS로 접근하였다.

기존 최솟값을 구하는 BFS 문제는 시작점이 하나였지만, 이번 토마토 문제에서는 시작점이 여러 곳일 가능성이 있었다. 그래서 토마토의 상태를 입력받으면서 익은 토마토를 나타내는 1이 들어오면 큐에 넣어주었다.

		for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
                if (graph[i][j] == 1) {
                    q.offer(new Point(i, j));
                }
            }
        }

다음 출력 조건이다.

1. 토마토가 모두 익지는 못하는 상황이면 -1을 출력
2. 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력

1번 조건을 만족하기 위해서 BFS 탐색 후 토마토의 상태를 기록해둔 그래프에서 0값이 발견되면 -1을 출력한다.

2번 조건을 만족하기 위해서 BFS 탐색을 하면서 움직인 거리의 값을 기록하는 distance 배열을 사용하였다. distance 배열은 이동 값 = 이동 전값 + 1 로 값을 저장한다. 1번 조건을 만족한 상황에서 distance 배열의 가장 큰 값을 출력하면 최소 날짜를 출력할 수 있고, 자연스럽게 2번 조건도 만족할 수 있다.

2번 조건을 만족할 수 있는 이유는 모두 익은 토마토 값이 입력되었다면 옆에 있는 토마토가 익어가는 상황이 없을 것이다. (이동하는 상황이 없다.) 따라서 distance 배열의 모든 값이 0일 것이다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point {
    int x, y;

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

public class Main {

    private static final int[] moveDirectionX = {1, 0, -1, 0};
    private static final int[] moveDirectionY = {0, 1, 0, -1};
    private static final int numberDirectionMovement = 4;

    static int n;
    static int m;
    static int[][] graph;
    static int[][] distance;
    static Queue<Point> q = new LinkedList<>();

    public void BFS() {


        while (!q.isEmpty()) {
            Point tmp = q.poll();
            for (int i = 0; i < numberDirectionMovement; i++) {
                int mX = tmp.x + moveDirectionX[i];
                int mY = tmp.y + moveDirectionY[i];
                if (0 <= mX && mX < n && 0 <= mY && mY < m && graph[mX][mY] == 0) {
                    distance[mX][mY] = distance[tmp.x][tmp.y] + 1;
                    graph[mX][mY] = 1;
                    q.offer(new Point(mX, mY));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        m = sc.nextInt();
        n = sc.nextInt();

        graph = new int[n][m];
        distance = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
                if (graph[i][j] == 1) {
                    q.offer(new Point(i, j));
                }
            }
        }

        new Main().BFS();
        boolean flag = true;
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 0) flag = false;
            }
        }

        if (flag) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    answer = Math.max(distance[i][j], answer);
                }
            }
            System.out.println(answer);
        } else {
            System.out.println(-1);
        }
    }
}