[JAVA] 백준 7576 토마토

1) 문제

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

2) 접근 방식

BFS로 풀어야 할 느낌이 났지만,,
익은 토마토들부터 시작하도록 동시에 BFS를 진행해야 할 것 같은데 어떻게 해야 하지? 에 대한 고민이 생겼다.
한 큐에 넣어버리면 먼저 도착하는 것이 더 높은건가..?
특히 익은 토마토들부터 시작해서 나중에는 뭔가 영역이 겹치는 날이 올 텐데 어떻게 해야 하지..?? 최솟값으로 해야 하나.. 이랬는데,,

이 부분에서 막혀서 다른 분의 풀이를 찾아보니

출처 : https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-7576%EB%B2%88-%ED%86%A0%EB%A7%88%ED%86%A0-Java-%EC%9E%90%EB%B0%94

익은 토마토들을 한 큐에 넣는데 depth를 현재 depth + 1 로 진행하기 때문에, 어느 토마토부터 시작하는지는 크게 중요하지 않은 것 같다.
그리고, 나중에 영역이 겹치게 되는 것에 대해서는,,
BFS는 너비 우선 탐색이니까 먼저 도착한 게 최소 일수여서! 먼저 도착해서 익은 게 장땡임.. 그래서 그냥 뭐 최솟값 따질 필요 없이.. 아직 안 익은 토마토인지만 판단해서 현재 depth + 1 만 진행해주면 된다...

나는 왜 이런 생각을 못 해낼까..
다음에 꼭 다시 풀어봐야겠다!!

3) 코드

import java.io.*;
import java.util.*;

public class Main {

    static int m, n;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Queue<Node> q = new LinkedList<>();

    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());
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    q.add(new Node(i, j));
                }
            }
        }

        System.out.println(bfs());
    }

    static int bfs() {
        while (!q.isEmpty()) {
            Node now = q.poll();
            int x = now.x;
            int y = now.y;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (map[nx][ny] == 0) {
                        map[nx][ny] = map[x][y] + 1;
                        q.offer(new Node(nx, ny));
                    }
                }
            }
        }

        int max = Integer.MIN_VALUE; // 모두 익을 때까지의 최소 날짜 -> 다 익으려면 가장 큰 값이어야 함
        if (checkZero()) { // 0이 있다는 것 = 토마토가 모두 익지 못하는 상황
            return -1;
        } else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map[i][j] > max) {
                        max = map[i][j];
                    }
                }
            }
            return max - 1;
        }
    }

    static boolean checkZero() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

class Node {
    int x;
    int y;

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