[ SW Expert Academy ] 5250. 최소 비용

1차 제출. [ 6 / 10 ] Fail

앗 .. 뭐지.. 시간초과로 터졌다...

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = 1e9
def bfs(board, n):
    dist = [[INF] * n for _ in range(n)]
    q = deque([(0, 0)])
    dist[0][0] = 0
    while q:
        x, y = q.pop()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                diff = 1
                if board[x][y] < board[nx][ny]:
                    diff += abs(board[x][y] - board[nx][ny])
                if dist[x][y] + diff < dist[nx][ny] :
                    dist[nx][ny] = dist[x][y] + diff
                    q.append((nx, ny))

    return dist[n-1][n-1]

T = int(input())
for test_case in range(1, T+1):
    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    answer = bfs(board, n)

    print("#{} {}".format(test_case, answer))

 

 

거의 비슷해보이는데.. 

왜 이 분 풀이는 시간이 안 터지지..? ㅠㅜ

 

와... 대박.. 나 진짜 왜이러니... 

그냥 실수인 걸 가지고 몇 시간을 .................... 와............... .............. ......

 

q에서 값을 꺼낼 때 선입선출해야해서 popleft()로 꺼내야 하는데 pop()으로 값을 꺼냈다...

테케는 도대체 왜 돌아가기는 한거지..? 와.. 허탈하고 실망스럽다..

덕분에 해당 알고리즘은 엄청 들여다봤으니.. 제대로 배웠다고 긍정적으로 생각해야하나.. 😒