[백준 Baekjoon] 7576번 토마토- JAVA

[백준 Baekjoon] 7576번 토마토- JAVA

---

문제 풀이

상자에 들어 있는 토마토가 모두 익을 때까지 최소 날짜를 출력하는 문제이다. 최소 날짜와 왼쪽, 오른쪽, 앞, 뒤 네 방향을 보고 bfs탐색으로 푸는 문제란 걸 알았다.

 

입력으로 주어진 토마토는 1 익은 토마토, 0 익지 않은 토마토, -1 토마토가 들어있지 않은 칸 이렇게 세 가지 종류이다.

bfs탐색으로 탐색해야 하는 칸(cnt)은 M * N (상자의 크기) - 익은 토마토 - 토마토가 들어있지  않은 칸이다.

 

익은 토마토에서 주변 토마토가 익기 때문에 큐에 모든 익은 토마토를 저장하고 bfs탐색을 한다. bfs 탐색으로 새로 탐색하는 칸은 방문하지 않았으며 토마토가 들어있지 않은 칸으로 새로 토마토가 익는 경우이다. 이 경우 cnt를 감소해주고 큐에 추가, visit배열에서 방문 체크해준다.

 

한번 큐에 들어있는 모든 토마토에 대해서 bfs탐색이 완료되면 날짜(answer)가 증가한다.

cnt가 0이 되면 모든 토마토가 익었으므로 날짜를 출력하고 종료한다.

 

소스 코드

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 Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][M];
        Queue<Node> queue = new LinkedList<>();
        boolean[][] visit = new boolean[N][M];
        int cnt = M * N;

        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) {
                    queue.add(new Node(i, j));
                    visit[i][j] = true;
                    cnt--;
                } else if (map[i][j] == -1) {
                    cnt--;
                }
            }
        }

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

        int answer = 0;
        while (!queue.isEmpty()) {
            if (cnt == 0) {
                System.out.println(answer);
                return;
            }

            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();

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

                    if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                    if (visit[nx][ny] || map[nx][ny] == -1) continue;

                    queue.add(new Node(nx, ny));
                    visit[nx][ny] = true;
                    cnt--;
                }
            }

            answer++;
        }

        System.out.println(-1);
    }

    public static class Node {
        int x;
        int y;

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