Inflearn Community Q&A

한번 그리디로 풀어봤는데 답이 안맞던데 그리디가 적용이 안되는 문제인가요?

코드는 아래와 같습니다.

from collections import deque

n = int(input())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, input().split())))

q = deque()
q.append((0, 0, matrix[0][0]))

while q:
    x, y, e = q.popleft()
    if x == y == n-1:
        print(e)
        break
    if x == n-1:
        q.append((x, y+1, e+matrix[x][y+1]))
    elif y == n-1:
        q.append((x+1, y, e+matrix[x+1][y]))
    elif matrix[x+1][y] >= matrix[x][y+1]:
        q.append((x, y+1, e+matrix[x][y+1]))
    elif matrix[x+1][y] < matrix[x][y+1]:
        q.append((x+1, y, e+matrix[x+1][y]))