[22.02.14] 이동하기 질문

[5Hyeons]

from collections import deque
import copy

def _input():
    return list(map(int, input().split()))

N, M = _input()
maze = [_input() for _ in range(N)]
new_maze = [[0]*M for _ in range(N)]
new_maze[0][0] = maze[0][0]

move = [(1, 0), (0, 1)]

q = deque([(0, 0)])
# BFS
while q:
    y, x = q.popleft()
    for my, mx in move:
        ny, nx = y + my, x + mx
        if 0 <= ny < N and 0 <= nx < M:
            if new_maze[ny][nx] < new_maze[y][x] + maze[ny][nx]:
                new_maze[ny][nx] = new_maze[y][x] + maze[ny][nx]
                q.append((ny, nx))

print(new_maze[N-1][M-1])

BFS로 풀었는데 틀렸습니다가 뜹니다.. 왜그럴까요. ㅠㅠ

현재까지의 누적 사탕 + 다음 사탕이 다음 좌표의 누적 사탕 보다 많을 때만 append하게 했습니다.

[5Hyeons]

[문제 확인]
제 코드는 아래와 같은 input 에 대해서 0을 출력하는 것을 확인하였습니다.
input
3 3
0 0 0
0 0 0
0 0 1
output
0

이후 코드 수정 후 해결했습니다