SWEA 5250. 최소비용 [Python]

• 문제 : 최소비용
• 난이도 : D3
• 언어 : python
• 문제 링크 : https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

def bfs(y, x):
    visited[y][x] = 0
    queue = []
    queue.append((y, x))
    while queue:
        cy, cx = queue.pop(0)
        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < N and 0 <= nx < N:
                # 배열의 다음 지점이 더 크면 다음 지점과 현재 지점의 높이차이 저장
                minus = 0
                if arr[cy][cx] < arr[ny][nx]:
                    minus = arr[ny][nx] - arr[cy][cx]

                # 연료 소비량 저장 (arr에서 다음 지점이 동일 값이면 1만 증가, 더 큰 값이 있으면 그 값의 차이인 minus + 1을 저장)
                if visited[cy][cx] + 1 + minus < visited[ny][nx]:
                    visited[ny][nx] = visited[cy][cx] + 1 + minus
                    queue.append((ny, nx))

    return visited[N-1][N-1]

T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [[100000] * N for _ in range(N)]

    print('#{} {}'.format(tc, bfs(0, 0)))