BFS(너비 우선 탐색): 백준 7576 파이썬 토마토

문제:

https://www.acmicpc.net/problem/7576

7576번: 토마토

풀이:

이 문제의 조건들을 잘 살펴보면 BFS를 사용해서 풀어야 하는 문제임을 알 수 있다.

1. 토마토를 익힐 수 있는 최소일 수
2. 주변의 토마토를 익힘
3. 간선의 가중치는 모두 1

입력받은 토마토 정보 중 익어있는 토마토의 좌표를 큐에 저장하고, bfs를 사용해 주변의 토마토들을 익혀 나가면

된다. 주변의 토마토가 익었다면 토마토 배열에 +1을 해주어 그래프에 익힌 일 수가 저장되도록 했다.

 

정답:

# '최소일 수, 주변의 토마토들을 익힘' -> bfs

import sys
from collections import deque
# deque 모듈을 사용하면 시간복잡도를 줄일 수 있다.(pop()은 O(n) popleft()는 O(1))

input = sys.stdin.readline

m, n = map(int, input().split())
# 토마토 정보를 이차원 리스트로 받기
tomato = [list(map(int, input().split())) for _ in range(n)]
# 좌표를 넣기 때문에 []를 넣어준다.
queue = deque([])
# 좌,우,위,아래로 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

result = 0

# queue에 처음 받은 토마토의 위치를 append
# n과 m 사용에 유의
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            queue.append([i, j])


def bfs():  # bfs 함수 정의
    while queue:
        # 처음 토마토 좌표 x,y를 꺼내어
        x, y = queue.popleft()
        # 처음 토마토 주변에 익힐 토마토가 있는지 찾아본다.
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            # 좌표가 n,m을 넘어가면 안되고, 해당 좌표에 토마토가 익지 않은 상태로 있어야 함
            if 0 <= nx < n and 0 <= ny < m and tomato[nx][ny] == 0:
                # 토마토를 익게 하고 횟수를 세어준다.
                tomato[nx][ny] = tomato[x][y] + 1
                queue.append([nx, ny])


bfs()
for i in tomato:
    for j in i:
        # 토마토를 익게하지 못했다면 -1 출력
        if j == 0:
            print(-1)
            exit(0)
    # 다 익게 했다면 최댓값을 추출
    result = max(result, max(i))

# 처음 시작을 1로 했으니 결괏값에는 1을 빼준다.
print(result - 1)