백준 7576 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

문제가 길다.

 

이 문제를 보고 전에 풀었던 미로 문제와 유사하다고 느꼈다.

 

하지만 문제가 있다.

 

토마토가 두 개가 존재하는 경우인데, 이 경우 때문에 bfs로 안 풀릴 거라 생각했었다.

 

결과적으로 bfs문제이다.

 

코드

from collections import deque

n, m = map(int,input().split())

array = []

max_val = 0

queue= deque()

for i in range(m):

    array.append(list(map(int,input().split())))

#    print(array[i],end='\n') # 처음입력된 배열

    if 1 in array[i]:

        queue.append((i,array[i].index(max(array[i]))))

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

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

def bfs():    

    while queue:

        y,x = queue.popleft()

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and array[ny][nx] == 0:

                queue.append((ny,nx))

                array[ny][nx] = array[y][x] + 1

bfs()

for i in range(m):

#    print(array[i],end='\n') # 토마토 익은 후 배열

    for j in range(n):

        if array[i][j] > max_val :

            max_val = array[i][j]

        elif array[i][j] == 0:

            max_val = 0

            break

    if max_val == 0:

        break

       

print(max_val-1)

하지만 이 코드는 정답이 아니다.

 

근데 왜 정답이 아닌지 모르겠다...

 

진짜 모르겠다

 

추후에 이유를 알게 되었을 때 추가해서 포스팅 하겠다.

 

배운 점

1. 토마토가 두 개일 경우에도, 큐에 순서대로 넣어주면 정상적인 탐색이 진행된다.