[백준 7576] 토마토 (Java)

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

7576번: 토마토

접근 방법

시작점이 여러 개인 bfs 문제였다.

 

현재 위치와 일수를 담는 Point 객체를 만들었고

탐색하는 동안 조건에 만족한 경우 큐에 넣었다.

 

조건은 다음과 같았다.

좌표가 박스 크기 범위 안인지(isInArea)

방문한 곳에 익지 않은 토마토가 있는지(0)

이미 방문한 곳이 아닌지(isVisited[x][y])

 

Point객체의 depth는 일수를 의미한다.

큐에 담길 때 현재 depth에서 1을 더해 담고

방문한 좌표에 대한 isVisited[x][y]를 true로 변경하고, box[x][y]를 1(익었음을 의미)로 바꿔줬다.

큐에서 꺼내올 때마다 해당 Point의 depth를 체크해 count 변수에 날짜를 업데이트 시켰다.

 

출력부분에서

box를 다시 탐색해 0이 한번이라도 있으면(익지 않은 토마토가 존재하면) - 1을 출력하고

그렇지 않으면 count를 출력했다.

 

 

소스 코드

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

public class Main {
    private static int N;
    private static int M;
    private static int[][] box;
    private static boolean[][] isVisited;
    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static int count = 0;

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

        M = scanner.nextInt();
        N = scanner.nextInt();

        box = new int[N + 1][M + 1];
        isVisited = new boolean[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                box[i][j] = scanner.nextInt();
            }
        }

        bfs();

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (box[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
            }
        }

        System.out.println(count);
    }

    private static void bfs() {
        Queue<Point> queue = new LinkedList<>();

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (box[i][j] == 1) {
                    queue.add(new Point(i, j, 0));
                    isVisited[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            count = Math.max(count, point.depth);

            for (int i = 0; i < 4; i++) {
                int x = point.x + dx[i];
                int y = point.y + dy[i];

                if (isInArea(x, y)) {
                    if (box[x][y] == 0 && !isVisited[x][y]) {
                        queue.add(new Point(x, y, point.depth + 1));
                        box[x][y] = 1;
                        isVisited[x][y] = true;
                    }
                }
            }
        }
    }

    private static boolean isInArea(int x, int y) {
        return x > 0 && x <= N && y > 0 && y <= M;
    }

    private static class Point {
        private int x;
        private int y;
        private int depth;

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