[baekjoon] 백준 7576번(파이썬): 토마토

문제

7576번: 토마토

- 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다.

- 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

- 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.

- 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

- 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.

- 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.

- 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

- 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

- 상자의 크기를 나타내는 두 정수 M,N이 주어진다.

- M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다.

- 단, 2 ≤ M,N ≤ 1,000 이다.

- 하나의 상자에 저장된 토마토들의 정보가 주어진다.

- 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

- 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

- 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.

- 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

알고리즘

- bfs를 통해 토마토 상자의 토마토를 모두 확인한다.

- 먼저 토마토 상자의 익은 토마토를 모두 확인한다.

- 익은 토마토 좌/우/아래/위 방향으로 확인하고 익지 않은 토마토가 있으면 익힌다.

- 이 과정을 재귀적으로 수행한다.

- 모든 익은 토마토 주위를 확인한 후 다시 한번 토마토 상자의 안 익은 토마토가 있는지 확인한다.

- 안 익은 토마토가 있으면 -1을 출력하고 그게 아니라면 일수에서 -1을 한 값을 출력한다.

이 문제를 풀고 밑에 링크에 있는 문제를 풀면 좋을 듯하다.

[baekjoon] 백준 7569번(파이썬): 토마토

코드

import sys
from collections import deque # deque를 통해 시간복잡도를 줄였다.


# bfs 탐색
def bfs(day):

    # 큐에 탐색해야 하는 노드 없을 때까지 실행
    while queue:

        day += 1  # 일수 증가

        # 큐에 있는 노드 수만큼 탐색
        for _ in range(len(queue)):

            a, b = queue.popleft()  # 큐에 있는(탐색해야 하는) 노드의 좌표
            # 4방향 확인
            for i in range(4):
                x = a + dx[i]
                y = b + dy[i]

                # 아직 방문하지 않은 미로중에 토마토가 있는 경우
                if -1 < x < n and -1 < y < m and graph[x][y] == 0:

                    # 방문처리
                    graph[x][y] = 1

                    # 탐색할 곳을 추가
                    queue.append([x, y])

    # 익지 않은 토마토 남아있는 경우 -1 반환
    for i in range(len(graph)):
        for j in range(len(graph[i])):
            if graph[i][j] == 0:
                return -1

    # 모두 익은 경우 일수 출력
    return day - 1


m, n = map(int, sys.stdin.readline().split())

# 2차원 미로
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 좌/우/위/아래 방향 이동
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 익은 토마토 확인
queue = deque([])
for i in range(len(graph)):
    for j in range(len(graph[i])):
        if graph[i][j] == 1:
            queue.append([i, j])

print(bfs(0))

github

junjange/CodingTest