[알고리즘] 백준7576 토마토 - 파이썬

어제 점심에 풀었던 문제였지만 졸업 프로젝트 포스터를 만들고 다른 과목 발표자료도 만드느라 이제야 글을 올린다..

 

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

7576번: 토마토

 

 

풀이코드

from collections import deque
from sys import stdin

m, n = map(int, stdin.readline().split()) # m가로, n세로

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

# print(graph)

# 상하좌우
xh = [-1, 1, 0, 0]
yw = [0, 0, -1, 1]

def bfs():
    while queue:
        x, y = queue.popleft()
        for d in range(4):
            xx = xh[d] + x
            yy = yw[d] + y
            if 0 <= xx < n and 0 <= yy <m and graph[xx][yy] == 0:
                graph[xx][yy] = graph[x][y] + 1
                queue.append([xx, yy])

queue = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append(([i,j])) # bfs함수 내부가 아닌 여기서 append를 해준다!!

bfs()
# print(graph) # bfs 수행 후 graph 점검

result = -2 # 임의로 설정한 최소값
flag = False # graph 탐색시 0인 값이 있다면 -1 출력위함
for row in graph:
    for r in row:
        if r == 0:
            flag = True
        result = max(result, r) # 최대값

if flag == True: print(-1)
elif result == -1: print(0) # 모두 익은 경우 : 0출력
else: print(result-1) # 결과 출력

 

문제풀이

: 이번에도 당연히 이차원 배열 graph [n-1][m-1]까지의 최소거리를 구하는 문제인 줄 알아서 어디가 문제인지 모르고 시간이 오래 걸렸던 문제였다.

그전에 풀었던 문제와 달리 이번 토마토 문제에서는 큐를 bfs함수 내부가 아닌 밖에 선언을 하고 이차원 배열을 돌면서 토마토가 존재하는 '1'인 인덱스들을! 큐에 append 해주어야 한다.

 

그렇지 않고 큐를 bfs함수 내부에서 생성하여 전에 문제를 풀 듯 큐에 하나의 인덱스만 넣고 돌리면 당연히 graph [n-1][m-1]까지의 최소거리를 구하는 코드가 되어버린다.

 

위 예제 입력 3)을 예로 들면 반복문을 돌면서 큐에 '1'인 인덱스인 0,0과 3,5가 담긴다 => deque([0,0]. [3,5])

그리고 bfs()를 수행하면  [0,0] out  [0,1] in => deque([3,5], [0,1]) 다음은 [3,5] out [2, 5] in => deque([[0,1], [2,5]) 이런 식으로 양쪽에서 좁혀오게 된다.