[Python/파이썬] 백준 7576 - 토마토

문제 설명

 

입출력 예제

 

---

풀이 코드

처음에는 시작지점의 인덱스 값을 bfs(x, y) 이런식으로 넘겨 탐색하도록 했지만 "예제 입력3"번 케이스에서만 계속 전혀 다른값이 나왔다.

이유는 다음과 같았다.

field[x][y]의 값이 1일 때 bfs(x,y)를 시작해 한칸씩 이동하는데, 예제 입력3번 케이스는 시작점이 2개이기 때문에

첫 번째 시작지점 탐색을 시작 할 때 field의 값을 +1씩 추가하고, 또 두번 째 시작지점에서도 bfs(x,y)를 시작해 field의 값을 +1 씩 추가하게 되어서 발생하는 문제였다.

 

이 부분을 해결하기 위해서는 queue의 특징을 이용해서 걍 시작점마다 한번씩 벌어가면서 탐색하도록 해야하는데 그러기 위해서는

시작점에 해당할 경우 먼저 queue에 시작점을 다 추가해놓고, 그 다음에 bfs를 실행하여 번갈아 가면서 탐색하도록 하면 된다.

 

정답 코드

from collections import deque
import sys
input = sys.stdin.readline

m, n = map(int, input().split()) # 열, 행
field = [list(map(int, input().split())) for _ in range(n)]
q = deque()
result = 0

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

zero_cnt = 0
for i in field:
    if 0 in i:
        zero_cnt += 1

# 이미 모든 토마토가 익어 있다면 0을 출력하고 종료
if zero_cnt == 0:
    print(0)
    exit(0)

def bfs():
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and field[nx][ny] == 0:
                q.append((nx, ny))
                field[nx][ny] = field[x][y] + 1

# 시작지점이 2개가 있을 때는 시작점을 서로 번갈아 가며 출발해야하므로 시작점을 먼저 q에 추가.
for x in range(n):
    for y in range(m):
        if field[x][y] == 1:
            q.append((x, y))

bfs()

for i in field:
    if 0 in i:
        print(-1)
        exit(0)
    result = max(result, max(i))
print(result - 1)