백준 7576 토마토

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

문제해결

이 문제는 시작점이 여러 개인 bfs 유형이다. 처음에 이 문제를 마주했을 때 어떻게 익은 토마토를 큐에 한 번에 넣을 수 있을지 고민했었다.

기본 bfs 구현에서 익은 토마토를 큐에 넣어주는 부분만 달라지고 크게 달라진 부분은 없다.
이 문제의 포인트는 익은 토마토와 인접하면서 안익은 토마토를 익은 토마토로 변경해주는 부분이라고 생각한다. 그래서 따로 방문여부를 체크하는 배열을 선언하지 않았다.
탐색이 끝난 후 토마토가 모두 익었는지 익지 않았는지 판별하기 위해 따로 check() 함수를 구현하여 0인 토마토가 있으면 -1 출력, 그렇지 않으면 토마토가 익은 일 수 day를 출력하였다.

소스코드

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 {
    static int n;
    static int m;
    static int[][] map;
    static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    static Queue<Node> queue;

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

    public static void bfs() {
        queue = new LinkedList<>();
        int day = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 익은 토마토라면 큐에 추가
                if (map[i][j] == 1) {
                    queue.add(new Node(i, j, 0)); // 처음 day = 0
                }
            }
        }
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            day = node.day;
            // 상하좌우 탐색
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                // 이동할 수 있으면서
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    // 안익은 토마토라면
                    if (map[nx][ny] == 0) {
                        // 익은 토마토로 변경
                        map[nx][ny] = 1;
                        queue.add(new Node(nx, ny, day + 1));
                    }
                }
            }
        }
        // 탐색 종료 후 토마토가 모두 익었으면 day 출력
        if (check()) {
            System.out.println(day);
            // 모두 익지 못하는 상황이면 -1 출력
        } else {
            System.out.println(-1);
        }
    }

    // 토마토가 모두 익었는지 안익었는지 확인하는 함수
    public static boolean check() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

// 좌표와 날짜
class Node {
    int x;
    int y;
    int day;

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