[Algorithm] 백준_7576 토마토 java

문제

M*N의 상자에 도마도가 있다. 0이 안 익은 토마토, 1은 익은 토마토, -1은 토마토가 들어있지 않은 칸이다.
보관 후 하루가 지나면 익은 토마토의 상하좌우에 있는 토마토들이 익는다. (대각선은 X)
상자에 있는 토마토가 익는 최소 일수를 구해 출력하면 되는 문제이다.

풀이

토마토를 입력받고, bfs를 사용해 토마토를 익힌다. 상하 좌우를 이동하며 범위 안에 있으면 이전 칸의 값에 +1을 해 해당 칸에 넣어준다.

|0|0|0|0|
|0|0|0|0|  
|0|0|0|0|
|0|0|0|1|

|0|0|0|0|
|0|0|0|2|   
|0|0|2|1|
|0|2|1|1|

이런 식으로 익은 토마토 상하 좌우에 1부터 시작해 day값을 늘리고 싶었으나 복잡해서 그냥

|7|6|5|4|
|6|5|4|3|   
|5|4|3|2|
|4|3|2|1|

이런 식으로 계산되게 하고, 가장 큰 값인 7에서 -1을 해 출력했다.

그리고 마지막에 check()함수를 통해 모든 토마토가 익었는지를 체크하고, 익지 않았으면 -1을 출력했다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_7576 {
    static int[][] board;
    static int M;
    static int N;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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());

        board = new int[N+1][M+1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bfs();

        int max = Integer.MIN_VALUE;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                max= Math.max(max, board[i][j]);
            }
        }

        if (check()) {
            System.out.println(max - 1);
        } else {
            System.out.println(-1);
        }
    }

    static void bfs() {
        Queue q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (board[i][j] == 1) {
                    q.add(new Tomato(i, j));
                }
            }
        }


        int nx, ny;
        while (!q.isEmpty()) {
            Tomato t = (Tomato) q.poll();

            int x = t.x;
            int y = t.y;

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

                if(nx <= 0 || nx > N || ny <= 0 || ny > M) continue;

                if (board[nx][ny] == 0) {
                    board[nx][ny] = board[x][y]+1;
                    q.add(new Tomato(nx, ny));
                }
            }
        }
    }

    static boolean check() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (board[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    static class Tomato {
        int x;
        int y;

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