백준 7576: 토마토

 

N × M 크기의 상자에 익은 토마토(1)와 익지 않은 토마토(0), 그리고 토마토가 들어있지 않은 칸(-1)이 있다. 익은 토마토는 하루가 지나면 상하좌우로 인접한 익지 않은 토마토를 익게 만든다. 모든 토마토가 익는 데 걸리는 최소 일수를 구하는 문제이다. 만약 모든 토마토를 익힐 수 없다면 -1을 출력해야 한다.

 

이 문제는 BFS(너비 우선 탐색) 을 활용하여 해결할 수 있다. BFS를 사용하면 여러 지점에서 동시에 탐색을 진행할 수 있으며, 최단 거리 계산에 유리하다.

---

2. BFS 알고리즘을 활용한 해결 방법

BFS 수행

• Queue를 사용하여 익은 토마토의 위치에서 시작하여 상하좌우로 탐색을 진행한다.
• 각 날짜마다 익는 토마토를 Queue에 추가하고, 하루가 지날 때마다 days 값을 증가시킨다.
• queue.size() 만큼만 반복하여 한 번의 BFS 반복이 하루를 의미하도록 한다.

결과 계산

• BFS 탐색이 끝난 후 map에 익지 않은 토마토(0)가 남아있으면 -1을 출력한다.
• 모든 토마토가 익었다면 days - 1을 출력한다. (days는 BFS의 반복 횟수이므로, 첫날을 제외한 실제 걸린 일수는 days - 1이다.)

---

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[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] map;
    static int days;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        map = new int[x][y];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < x; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < y; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) queue.offer(new int[] {i, j});
            }
        }

        bfs(queue);
        
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (map[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
            }
        }

        System.out.println(days - 1);

    }

    static void bfs(Queue<int[]> queue) {
        days = 0;

        while (!queue.isEmpty()) {

            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] arr = queue.poll();
                int nowX = arr[0];
                int nowY = arr[1];

                for (int k = 0; k < 4; k++) {
                    int nextX = nowX + dx[k];
                    int nextY = nowY + dy[k];

                    if (nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] == 0) {
                        queue.offer(new int[] {nextX, nextY});
                        map[nextX][nextY] = 1;
                    }
                }
            }

            days++;

        }

    }


}

1) BFS 탐색을 위한 방향 배열

• BFS 탐색 시, 상하좌우 방향으로 이동하기 위한 배열이다.

2) 초기 토마토 위치를 Queue에 저장

• 익은 토마토(1)를 BFS 탐색의 시작점으로 Queue에 저장한다.

3) bfs() 함수에서 BFS 탐색 진행

• queue.size() 만큼 반복하여 한 번의 루프가 하루를 의미하도록 구현한다.

• poll()을 이용해 현재 익은 토마토를 꺼내고, 상하좌우의 익지 않은 토마토를 익게 한다.

• 방문한 칸을 1로 변경하여 중복 방문을 방지한다.

• 하루가 끝날 때마다 days++ 증가시킨다.

4) 결과 계산

• BFS 수행 후에도 익지 않은 토마토(0)가 남아있다면 -1을 출력한다.

• 모든 토마토가 익었다면 days - 1을 출력한다.

 

5. 시간 복잡도 분석

• BFS의 시간 복잡도는 O(NM) (N: 행 개수, M: 열 개수)
• Queue를 사용하여 모든 노드를 한 번씩 탐색하므로 효율적인 해결 방법이다.