알고리즘) 토마토(백준 7576번, 트리 탐색 BFS)

문제 ✨

문제(백준)

풀이 ✨

 좌표(Point)를 저장하는 큐를 생성한다. 처음에 각 좌표의 값(0 또는 1 또는 -1)을 입력받을 때 1인 경우에는 미리 큐에 넣어두어 첫 날에 4방위를 토마토를 익게 하는 기준점들이 되게 한다. 상하좌우의 좌표를 확인하기 위해 y축에서 이동해야 하는 수와 x축에서 이동해야 하는 수를 크기가 4인 배열로 각각 만들어서 그 좌표가 1 ~ N 또는 1 ~ M의 크기이고, 그 값이 0이라면 1로 변화시킨다.

 주의해야 할 점은, 검사한 좌표의 값이 -1일 경우에는 변화할 수 없으며 처음에 입력받을 때 좌표 값이 -1인 경우 1일 때와 같이 cnt를 올린다.

작성 코드 ✍️

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

public class Main {
    static int m;
    static int n;
    static int[][] matrix;
    static int days = 0;
    static int cnt = 0;
    static int[] ym = {-1, 0, 1, 0};
    static int[] xm = {0, 1, 0, -1};
    static Queue<Point> q = new LinkedList<>();

    static class Point {
        int y;
        int x;

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

    void BFS() {
        while (!q.isEmpty()) {
            int size = q.size();
            if (cnt == n * m) return;
            else {
                for (int j = 0; j < size; j++) {

                    Point p = q.poll();
                    for (int i = 0; i < 4; i++) {
                        int my = p.y + ym[i];
                        int mx = p.x + xm[i];
                        if (my > 0 && my <= n && mx > 0 && mx <= m) {
                            if (matrix[my][mx] == 0) {
                                matrix[my][mx] = 1;
                                q.offer(new Point(my, mx));
                                cnt++;
                            }
                        }
                    }
                }
            }
            days++;
        }

        if (cnt < n * m) days = -1;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        matrix = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int status = sc.nextInt();
                matrix[i][j] = status;
                if (status == 1) {
                    q.offer(new Point(i, j));
                }
                if (status == 1 || status == -1) cnt++;
            }
        }

        main.BFS();
        System.out.println(days);
    }
}