[BOJ] 7576: 토마토 (JAVA)

문제

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

 

여담

익어있는 토마토가 여러 개 주어질 수 있으므로, 익어있는 토마토들의 위치를 미리 큐에 넣는 작업이 필요하다. 이 과정에서 큐에 넣기만 하고 방문 처리를 하지 않아서 틀렸었다..

 

뒤늦게라도 알아서 다행이지만 코테였다면 이유를 찾느라 고생했을 것이다. 아찔... 익숙한 문제라고 뇌 빼고 풀지 말고 차근차근 풀도록 하자!

 

풀이

토마토들이 모두 익을 수 있는 최소 일수를 구하는 문제이다. 즉, 최단 거리를 구하는 문제와 비슷하므로 BFS 탐색을 수해하면 된다. 

 

문제 풀이 과정은 다음과 같다.

1. 익은 토마토들이 1개 이상 주어지므로, 익은 토마토들의 위치를 큐에 저장하고 방문 처리한다.
2. BFS 탐색을 수행하여 토마토들이 익는 일수를 구한다.
   • box[nx][ny] = box[now.x][now.y] + 1
3. 큐가 비었다면 모든 토마토들이 익었는지 확인한다.
   • 토마토가 다 익지 못했다면 -1을 출력한다.
   • 토마토가 다 익었다면 최소 일수를 출력한다.

 

코드

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

public class Main {
    static int M, N;
    static int[][] box;
    static boolean[][] visited;
    static Queue<Pos> queue = new LinkedList<>();
    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());
        box = new int[N][M];
        visited = new boolean[N][M];

        int tomato = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
                if (box[i][j] != -1) tomato++;
                if (box[i][j] == 1) { // 익은 토마토 위치 저장하기
                    queue.offer(new Pos(i, j));
                    visited[i][j] = true;
                }
            }
        }

        if (tomato == queue.size()) { // 저장될 때부터 모든 토마토가 익어있는 상태일 때
            System.out.println(0);
            return;
        }
        
        System.out.println(bfs());
    }

    public static int bfs() {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!queue.isEmpty()) {
            Pos now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny] || box[nx][ny] == -1) {
                    continue;
                }

                queue.offer(new Pos(nx, ny));
                visited[nx][ny] = true;
                box[nx][ny] = box[now.x][now.y] + 1;
            }
        }

        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (box[i][j] == 0) return -1; // 토마토가 모두 익지 못하는 경우
                max = Math.max(max, box[i][j]);
            }
        }
        return max - 1;
    }

    static class Pos {
        int x, y;

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

---