[알고리즘 / 백준] 7576 - 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

 

문제는 위와 같으며, 이 문제는 우선순위 큐와 BFS 를 사용하여 해결하였습니다.

 

먼저 토마토의 위치를 이차원 배열로 저장하고, 우선순위 큐를 생성하여 처음부터 익어있는 토마토를 우선 저장합니다.

우선순위 큐에 토마토를 저장할 때, [익는데 걸리는 일수, 토마토의 x 좌표, 토마토의 y 좌표] 형태로 데이터를 저장합니다. 이렇게 익는데 걸리는 일수를 기준으로 우선순위 큐에 데이터를 저장하게 되면, 같은 위치의 토마토가 익었는지 확인할 때 걸리는 최소 일수를 쉽게 구할 수 있습니다.

 

그런 다음 우선순위 큐에 데이터가 없을 때까지 반복해서 주변 토마토를 확인하게 됩니다. 아래, 위, 우, 좌 순서대로 주변 토마토를 확인하며 다음 토마토가 상자 내에 존재하고 아직 익지 않았다면(한번도 해당 위치를 확인한 적이 없는 경우) 익은 토마토로 처리하고 우선순위 큐에 [다음 토마토가 익는데 걸리는 일수(현재 토마토가 익는데 걸리는 일수 + 1), 다음 토마토의 x 좌표, 다음 토마토의 y 좌표] 데이터를 저장합니다. 그리고 다음 토마토까지 확인하는데 걸리는 최대 일수를 저장해둡니다.

 

마지막으로 주변 토마토들을 모두 확인한 뒤에도 아직 익지 않은 토마토가 있는지 확인하여, 있다면 -1 을 출력하고 종료할 수 있도록 합니다. 그렇지 않은 경우는 이전에 저장해둔 최대 일수를 그대로 출력합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs():
    total_day = 0

    queue = []
    # 초기 익은 토마토 확인
    for i in range(n):
        for j in range(m):
            if tomato[i][j] == 1:  # 이미 익은 토마토가 주어진 경우
                heapq.heappush(queue, [0, i, j])  # [익는데 걸리는 일수, 토마토 위치 x, 토마토 위치 y] 데이터를 우선순위 큐에 저장

    while queue:
        day, x, y = heapq.heappop(queue)  # 익는데 걸리는 일수가 적은 토마토부터 순차적으로 확인
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < n and 0 <= ny < m:  # 주변(상하좌우) 토마토의 위치가 상자 범위 내에 있고
                if tomato[nx][ny] == 0:  # 아직 토마토가 익지 않은 경우
                    tomato[nx][ny] = 1  # 토마토가 익은 것으로 처리하고
                    heapq.heappush(queue, [day + 1, nx, ny])  # 해당(다음) 토마토를 [현재 토마토가 익는데 걸리는 일수 + 1, 토마토 위치 x, 토마토 위치 y] 데이터를 우선순위 큐에 저장
                    total_day = max(total_day, day + 1)  # 지금까지 토마토가 익는데 걸린 시간과 확인된 토마토가 익는데 걸리는 일수 중 더 큰 값을 저장

    # 최종적으로 익지 않은 토마토가 있는지 확인
    for i in range(n):
        for j in range(m):
            if tomato[i][j] == 0:
                return -1

    return total_day


m, n = map(int, stdin.readline().split())
tomato = []
for _ in range(n):
    tomato.append(list(map(int, stdin.readline().split())))

print(bfs())

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int[][] tomato = new int[n][m];
        for (int i = 0; i < n; i++) {
            tomato[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

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

        int total_day = 0;
        // 우선순위 큐에 [익는데 걸리는 일수, x, y] 데이터를 저장할 때
        // 익는데 걸리는 일수를 기준으로 우선순위를 정하도록 지정
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] t1) {
                return ints[0] - t1[0];
            }
        });
        
        // 처음부터 익은 토마토 확인
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tomato[i][j] == 1) {
                    queue.offer(new int[]{0, i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] t = queue.poll();  // 익는데 걸리는 일수가 적은 순으로 먼저 확인
            for (int i = 0; i < 4; i++) {
                int nx = t[1] + dx[i];
                int ny = t[2] + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {  // 다음 토마토가 상자 안에 있고
                    if (tomato[nx][ny] == 0) {  // 아직 익지 않은 토마토인 경우
                        tomato[nx][ny] = 1;  // 익음 처리
                        queue.offer(new int[]{t[0] + 1, nx, ny});  // [다음 토마토가 익는데 걸리는 일수(현재 토마토가 익는데 걸리는 일수 + 1), 다음 토마토 x, 다음 토마토 y] 데이터를 우선순위 큐에 저장
                        total_day = Math.max(total_day, t[0] + 1);  // 익는데 걸리는 최대 시간 확인
                    }
                }
            }
        }

		// 최종적으로 익지 않은 토마토 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tomato[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
            }
        }

        System.out.println(total_day);
    }
}