[BOJ/Java] 토마토 (7576)

토마토 (7576)

1. 문제 분석

문제 개요

• 토마토 상자에서 모든 토마토가 익는 데 걸리는 최소 일수를 구하는 문제이다.
• 상자에서 익은 토마토가 인접한 익지 않은 토마토를 익게 한다.
• 상자에 토마토가 없는 곳은 -1로 표시된다.

입력 형식

• 첫째 줄에 두 정수 M과 N이 주어진다. (1 ≤ M, N ≤ 1000)
• 다음 N개의 줄에 M개의 정수로 이루어진 상자의 모양이 주어진다.
  • 1은 익은 토마토
  • 0은 익지 않은 토마토
  • -1은 토마토가 없는 곳

출력 형식

• 모든 토마토가 익는 데 걸리는 최소 일수를 출력한다.
• 만약 모든 토마토를 익히는 것이 불가능하면 -1을 출력한다.

2. 알고리즘 종류

• 이 문제는 그래프 탐색 문제로, 너비 우선 탐색 (BFS)를 사용하여 익은 토마토가 인접한 익지 않은 토마토를 익히는 과정을 시뮬레이션한다.

3. 주요 부분 및 코드 작성 방법

1. 입력 처리 및 초기화

• 입력을 통해 상자의 크기와 모양을 저장하고, 익은 토마토의 위치를 큐에 저장한다.

2. BFS를 통한 토마토 익히기

• BFS를 사용하여 익은 토마토가 인접한 익지 않은 토마토를 익히는 과정을 시뮬레이션한다.
• 각 토마토의 익는 날을 기록하고, 큐에서 처리된 토마토의 날을 기반으로 인접한 토마토를 익히고 큐에 추가한다.

3. 결과 확인 및 출력

• 모든 토마토가 익었는지 확인하고, 익지 않은 토마토가 남아 있으면 -1을 출력한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리 및 초기화

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
    StringTokenizer st = new StringTokenizer(br.readLine()); // 첫 번째 줄 입력 처리
    M = Integer.parseInt(st.nextToken()); // 상자의 열 수 M 입력
    N = Integer.parseInt(st.nextToken()); // 상자의 행 수 N 입력
    box = new int[N][M]; // 상자를 저장할 2차원 배열 생성
  
    // 상자에 토마토 저장 (1 : 익은 토마토 / 0 : 익지 않은 토마토 / -1 : 토마토 X)
    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) queue.offer(new tomato(i, j, 0)); // 익은 토마토를 큐에 추가
        }
    }

  • BufferedReader와 StringTokenizer를 사용하여 입력을 처리하고, 상자의 크기에 맞게 배열을 초기화한다.
  • 익은 토마토를 큐에 추가하여 BFS를 위한 초기 상태를 설정한다.

• BFS를 통한 토마토 익히기

    public static void bfs() {
        // 익은 토마토의 인접 토마토 영향
        while (!queue.isEmpty()) {
            tomato t = queue.poll(); // 큐에서 토마토를 꺼낸다
            days = t.day; // 현재 토마토가 익은 날 저장
  
            for (int i = 0; i < 4; i++) {
                int nx = t.x + dx[i];
                int ny = t.y + dy[i];
  
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue; // 경계 검사
                if (box[nx][ny] == 0) { // 익지 않은 토마토가 있는 경우
                    box[nx][ny] = 1; // 토마토를 익게 만든다
                    queue.add(new tomato(nx, ny, days + 1)); // 익은 날을 업데이트하여 큐에 추가
                }
            }
        }
        if (check()) System.out.println(days); // 모든 토마토가 익었으면 최종 일수 출력
        else System.out.println(-1); // 익지 않은 토마토가 남아 있으면 -1 출력
    }

  • 큐에서 토마토를 꺼내며 BFS를 수행하고, 상하좌우 4방향을 검사하여 익지 않은 토마토를 익힌다.
  • 모든 토마토가 익었는지 확인하고, 결과를 출력한다.

(2) 토마토 익음 확인 함수 (check)

• 모든 토마토가 익었는지 확인

    public static boolean check() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (box[i][j] == 0) return false; // 익지 않은 토마토가 있으면 false 반환
            }
        }
        return true; // 모든 토마토가 익었으면 true 반환
    }

  • 상자의 모든 위치를 순회하며 익지 않은 토마토가 있는지 검사한다.
  • 익지 않은 토마토가 있으면 false를 반환하고, 모든 토마토가 익었으면 true를 반환한다.

5. 전체 코드

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

public class Main {
    static int M, N, days;
    static int[][] box; // 상자를 저장할 2차원 배열
    static Queue<tomato> queue = new LinkedList<tomato>(); // BFS를 위한 큐

    static int[] dx = {-1, 1, 0, 0}; // 상하좌우 방향 벡터
    static int[] dy = {0, 0, 1, -1}; // 상하좌우 방향 벡터

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        StringTokenizer st = new StringTokenizer(br.readLine()); // 첫 번째 줄 입력 처리
        M = Integer.parseInt(st.nextToken()); // 상자의 열 수 M 입력
        N = Integer.parseInt(st.nextToken()); // 상자의 행 수 N 입력
        box = new int[N][M]; // 상자를 저장할 2차원 배열 생성

        // 상자에 토마토 저장 (1 : 익은 토마토 / 0 : 익지 않은 토마토 / -1 : 토마토 X)
        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) queue.offer(new tomato(i, j, 0)); // 익은 토마토를 큐에 추가
            }
        }

        bfs(); // BFS를 수행하여 결과를 계산
    }

    public static void bfs() {
        // 익은 토마토의 인접 토마토 영향
        while (!queue.isEmpty()) {
            tomato t = queue.poll(); // 큐에서 토마토를 꺼낸다
            days = t.day; // 현재 토마토가 익은 날 저장

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue; // 경계 검사
                if (box[nx][ny] == 0) { // 익지 않은 토마토가 있는 경우
                    box[nx][ny] = 1; // 토마토를 익게 만든다
                    queue.add(new tomato(nx, ny, days + 1)); // 익은 날을 업데이트하여 큐에 추가
                }
            }
        }
        if (check()) System.out.println(days); // 모든 토마토가 익었으면 최종 일수 출력
        else System.out.println(-1); // 익지 않은 토마토가 남아 있으면 -1 출력
    }

    public static boolean check() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (box[i][j] == 0) return false; // 익지 않은 토마토가 있으면 false 반환
            }
        }
        return true; // 모든 토마토가 익었으면 true 반환
    }
}