백준 7576번 - 토마토[BFS/Java]

 

문제 설명

철수의 토마토 농장에는 여러 상자에 토마토가 보관되어 있다. 상자의 크기는 N×M 크기의 격자 형태로 구성되며, 각 칸에는 익은 토마토(1), 익지 않은 토마토(0), 또는 빈 칸(-1)이 존재할 수 있다. 하루가 지나면 익은 토마토는 인접한 네 방향(상, 하, 좌, 우)에 있는 익지 않은 토마토를 익게 만든다. 모든 토마토가 익는 데 걸리는 최소 일수를 계산해야 한다. 만약 익지 않은 토마토가 존재하나, 모두 익지 못하는 경우 -1을 출력하고, 처음부터 모든 토마토가 익어 있으면 0을 출력한다.

 

문제 접근

이 문제는 최단 거리 탐색 문제로, 너비 우선 탐색(BFS, Breadth-First Search)를 통해 풀 수 있다. BFS는 시작점에서 가까운 노드부터 차례대로 탐색하는 방법으로, 인접한 노드로 퍼져나가며 탐색하는 특성을 가진다. 이 문제에서는 익은 토마토가 익지 않은 토마토로 익음 상태를 전파하는 과정을 BFS로 구현할 수 있다.

1. 입력받은 상태에서 익은 토마토를 큐에 넣어 BFS 탐색을 시작한다.
2. 상하좌우로 이동하며 익지 않은 토마토를 익은 상태로 바꾸고, 해당 토마토가 익을 때까지 걸린 시간을 기록한다.
3. 모든 토마토가 익었다면 최소 일수를 출력하고, 그렇지 않으면 -1을 출력한다.

풀이 과정

1. 입력 처리 및 초기화

• N×M 크기의 창고 정보를 입력받는다.
• 익은 토마토(1)의 위치를 파악하여 BFS의 시작점으로 설정하고 큐에 넣는다.
• 익은 토마토가 없는 칸(-1)은 BFS에서 제외된다.

2. BFS 탐색

• 큐에서 익은 토마토의 위치를 하나씩 꺼내고, 상하좌우로 이동하면서 익지 않은 토마토(0)를 익은 토마토(1)로 바꾼다.
• 토마토가 익는 과정에서 일수를 dis 배열에 기록하여 나중에 계산할 수 있도록 한다.
• 인접한 모든 토마토를 익게 한 후, 새롭게 익은 토마토들을 다시 큐에 넣어 계속 탐색을 이어나간다.

3. 결과 계산 및 출력

• BFS 탐색이 완료된 후, 창고를 다시 확인하여 익지 않은 토마토(0)가 남아 있는지 검사한다.
• 남아있다면 -1을 출력하고, 모두 익었다면 익는데 걸린 최대 일수를 출력한다.

코드

package com.example.codingtest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
    int x, y;

    // 좌표를 저장할 Point 클래스 생성자
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Main {
    // 상하좌우 탐색을 위한 dx, dy 배열
    static int[] dx = {-1, 0, 1, 0}; // 상, 우, 하, 좌의 x 좌표 변화
    static int[] dy = {0, 1, 0, -1}; // 상, 우, 하, 좌의 y 좌표 변화
    static int[][] board, dis; // 토마토 상태를 저장하는 배열(board)과 일수를 저장하는 배열(dis)
    static int N, M; // N은 세로, M은 가로 크기
    static Queue<Point> Q = new LinkedList<>(); // BFS 탐색을 위한 큐 선언

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 위한 BufferedReader
        String[] str = br.readLine().split(" "); // 첫 번째 줄에서 N과 M을 입력받음
        M = Integer.parseInt(str[0]); // 가로 칸의 수 M
        N = Integer.parseInt(str[1]); // 세로 칸의 수 N

        board = new int[N][M]; // 토마토 상태를 저장할 배열 초기화
        dis = new int[N][M]; // 날짜를 저장할 배열 초기화

        // 토마토 상태를 입력받는 부분
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                if (st.hasMoreTokens()) {
                    board[i][j] = Integer.parseInt(st.nextToken()); // 토마토 상태 저장
                    if (board[i][j] == 1) { // 익은 토마토일 경우
                        Q.offer(new Point(i, j)); // 큐에 해당 좌표를 넣어 BFS 시작점으로 설정
                    }
                }
            }
        }
        BFS(); // BFS 탐색 시작
        System.out.println(checkTomato()); // 탐색 후 결과 출력
    }

    // BFS 탐색을 통한 토마토 익히기
    public static void BFS() {
        while (!Q.isEmpty()) { // 큐가 빌 때까지 반복
            Point tmp = Q.poll(); // 큐에서 좌표를 꺼냄
            for (int i = 0; i < 4; i++) { // 상하좌우 네 방향 탐색
                int nx = tmp.x + dx[i]; // 새로운 x 좌표
                int ny = tmp.y + dy[i]; // 새로운 y 좌표

                // 새 좌표가 유효한지 확인 (창고 범위 내, 익지 않은 토마토일 때만)
                if (nx >= 0 && nx < N && ny >= 0 && ny < M && board[nx][ny] == 0) {
                    board[nx][ny] = 1; // 익지 않은 토마토를 익음으로 변경
                    Q.offer(new Point(nx, ny)); // 새로운 익은 토마토 좌표를 큐에 넣음
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1; // 현재 좌표까지 걸린 일수를 기록
                }
            }
        }
    }

    // 결과를 체크하는 메서드
    public static int checkTomato() {
        int result = 0;

        // 모든 토마토의 상태를 확인
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0) { // 익지 않은 토마토가 있으면 -1 리턴
                    return -1;
                }
                result = Math.max(result, dis[i][j]); // 최대 일수를 갱신
            }
        }
        return result; // 최소 일수를 리턴
    }
}

풀이 설명

1. 입력 처리

• 첫 번째 줄에서 창고의 크기 M과 N을 입력받고, 두 번째 줄부터는 창고 내 각 칸의 토마토 상태를 입력받는다.
• 토마토 상태는 1(익은 토마토), 0(익지 않은 토마토), -1(토마토가 없는 칸)으로 주어진다.
• 익은 토마토는 BFS의 시작점으로 설정하며, 큐에 넣어 탐색을 준비한다.

2. BFS 탐색

• 큐에 저장된 익은 토마토의 좌표를 기준으로 상하좌우에 있는 익지 않은 토마토를 찾아 익게 만든다.
• 이때 토마토가 익는 데 걸린 일수를 dis 배열에 기록하여, 최종적으로 모든 토마토가 익을 때까지 며칠이 걸리는지 계산한다.

3. 결과 확인

• BFS 탐색이 완료된 후, 창고 내에 익지 않은 토마토가 남아 있는지 확인한다.
• 익지 않은 토마토가 있다면 -1을 반환하고, 그렇지 않으면 걸린 일수 중 가장 큰 값을 반환한다.