[백준] 7576번 토마토

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

7576번: 토마토

 

익지 않은 토마토의 카운트를 세서

익었다는 처리를 할 때 빼줌

방문여부를 누적해서 최종 날짜를 셈

 

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

class Node {
    int y;
    int x;

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

public class Main {

    // 가로
    static int M;
    // 세로
    static int N;

    static int[][] map;
    static int[][] visit;

    static int[] dy = { 0, 1, 0, -1 };
    static int[] dx = { 1, 0, -1, 0 };

    // 안익은 토마토
    static int count = 0;
    // 날짜
    static int day = 0;

    static Queue<Node> q = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        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];
        visit = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                // 방문여부 초기화
                visit[i][j] = -1;
                int tomato = Integer.parseInt(st.nextToken());
                map[i][j] = tomato;
                if (tomato == 1) {
                    q.offer(new Node(i, j)); // 토마토가 익었을 때 큐에 넣어줌
                    visit[i][j] = 0;
                } else if (tomato == 0) { // 안 익은 토마토 카운트 올려줌
                	count++;
                }

            }
        }

        // 안 익은 토마토 없으면 종료
        if (count == 0) {
            System.out.print(0);
            System.exit(0);
        }

        bfs();

        // 아직 안 익은 토마토가 남아 있으면
        if (count > 0) {
        	System.out.println(-1);
        } else {
        	System.out.println(day);
        }
    }

    public static void bfs() {
        // 1 이미 익은거
        // 0 안익은거
        // -1 없는거
        while (!q.isEmpty()) {
            Node node = q.poll();
            for (int i = 0; i < 4; i++) {
                int ny = dy[i] + node.y;
                int nx = dx[i] + node.x;

                // 범위 벗어날 때
                if (ny < 0 || ny >= N || nx < 0 || nx >= M) {
                	continue;
                }
                // 토마토 없거나 이미 방문했을 경우
                if (map[ny][nx] == -1 || visit[ny][nx] != -1) {
                	continue;
                }
                // 익은 토마토 큐에넣어주고
                q.offer(new Node(ny, nx));
                // 안 익은 거에서 빼줌
                count--;
                // 방문여부를 현재노드 + 1
                visit[ny][nx] = visit[node.y][node.x] + 1;

                // 해당 날짜가 최종인지 구분
                if (day < visit[ny][nx]) {
                	day = visit[ny][nx];
                }
            }
        }
    }
}