[백준] 7576번 : 토마토 - 자바[Java]

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

풀이

대표적인 BFS 문제다.

토마토 상태를 입력받을 때 익지 않은 토마토의 개수를 미리 카운트하고, BFS를 하며 익은 토마토의 개수를 카운트한다.

BFS가 종료된 후 익지 않은 토마토가 있다면 -1을 출력하고, 모두 익었다면 모두 익을 때까지의 걸린 시간을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m;
    static int[][] map;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

    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];
        Queue<int[]> q = new ArrayDeque<>();

        int notTomato = 0; // 익지 않은 토마토 개수
        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] == 0) {
                    notTomato++;
                }
                else if (map[i][j] == 1) { // 익은 토마토의 위치를 큐에 추가
                    q.add(new int[] {i, j});
                }
            }
        }

        int time = 0;

        // BFS
        while (!q.isEmpty()) {
            if (notTomato == 0) { // 토마토가 모두 익었다면 BFS 종료
                break;
            }
            int size = q.size();
            while (size-- > 0) {
                int[] cur = q.poll();

                // 4방향 검사
                for (int d = 0; d < 4; d++) {
                    int nr = cur[0] + dr[d];
                    int nc = cur[1] + dc[d];

                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && map[nr][nc] == 0) {
                        map[nr][nc] = 1;
                        notTomato--;
                        q.add(new int[] {nr, nc});
                    }
                }
            }
            time++;
        }

        if (notTomato != 0) {
            time = -1;
        }

        System.out.println(time);
    }

}

다른 풀이

옛날에 풀었던 풀이다.

배열에 해당 토마토가 익기까지의 시간을 저장하고, 이중 for문을 통해 최댓값을 구한 후 -1을 한 값을 출력한다.

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

public class Main {

    static class Point {
        int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

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

    public static int bfs(int[][] arr, int n, int m, Queue<Point> tomato) {

        while (!tomato.isEmpty()) {

            Point cur = tomato.poll();

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == 0) {
                    arr[nx][ny] = arr[cur.x][cur.y] + 1;
                    tomato.offer(new Point(nx, ny));
                }
            }

        }

        int days = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 0)
                    return -1;
                days = Math.max(days, arr[i][j]);
            }
        }

        return days-1;
    }

    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[][] arr = new int[n][m];
        Queue<Point> tomato = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int tmp = Integer.parseInt(st.nextToken());
                arr[i][j] = tmp;

                if (tmp == 1)
                    tomato.add(new Point(i, j));
            }
        }

        System.out.println(bfs(arr, n, m, tomato));

    }
}