[SWEA] 5250_최소 비용

📕 문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

💡 풀이법

1. 다익스트라 알고리즘을 이용했다.

2. matrix와 크기가 같은 2차행렬 dp를 만들어준다.

3. 0,0 부터 시작을 한다.

4. 현재 위치에서 사방을 탐색하고 갈 수 있는 위치라면 다음 위치가 현재위치보다 높이가 더 높다면 그 차이를 계산해서 가중치를 구한다.

5. 만약  dp에서 다음위치의 값이 현재 위치에서 가중치를 더한 값보다 크다면 deq에 다음 위치를 담아주고, dp의 값을 바꿔준다.

(dp값이 현재위치에서 가중치를 더한 값보다 작다면 그 곳을 더이상 탐색할 이유가 없기 때문에)

6. 결국 dp에서 도착점의 위치의 값이 최소 연료 소비량이 된다.

 

from collections import deque
dxy = [(0,1),(1,0),(-1,0),(0,-1)]

def dijkstra(x,y):
    dxy = [(1,0),(0,1),(-1,0),(0,-1)]
    deq = deque([(x, y)])
    dp[x][y] = 0

    while deq:
        x, y = deq.popleft()

        for dx, dy in dxy:
            nx, ny = x + dx, y + dy

            if -1 < nx < N and -1 < ny < N:
                diff = 0
                if matrix[nx][ny] > matrix[x][y]:
                    diff += matrix[nx][ny] - matrix[x][y]

                if dp[nx][ny] > dp[x][y] + diff + 1:
                    deq.append((nx, ny))
                    dp[nx][ny] = dp[x][y] + diff + 1


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    dp = [[float('inf') for _ in range(N)] for _ in range(N)]
    ans = float('inf')
    dijkstra(0,0)
    print('#{} {}'.format(tc, dp[N-1][N-1]))