티스토리 뷰

백준

백준 7576 문제풀이 [python]

ys.k 2023. 6. 19. 16:12

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

문제를 보자.

문제가 길다.

 

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

 

하지만 문제가 있다.

 

토마토가 두 개가 존재하는 경우인데, 이 경우 때문에 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. 토마토가 두 개일 경우에도, 큐에 순서대로 넣어주면 정상적인 탐색이 진행된다.

'백준' 카테고리의 다른 글

백준 2667 문제풀이 [python]  (0) 2023.06.19
백준 2751번 문제풀이 [python]  (0) 2023.06.19
백준 15552번 문제풀이 [python]  (0) 2023.06.18
백준 2309 문제풀이 [python]  (0) 2023.06.17
백준 2609 문제풀이 [python]  (0) 2023.06.17
댓글