최소비용 Python(SW Expert Academy, SWEA)

난이도 : D3

문제번호 : 5250

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYHO7a2JoDFAVT#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

출발에서 최종 도착지까지 경유하는 지역의 높이 차이에 따라 연료 소비량이 달라지기 때문에, 최적의 경로로 이동하면 최소한의 연료로 이동할 수 있다. 다음은 각 지역의 높이를 기록한 표의 예로, 항상 출발은 맨 왼쪽 위, 도착지는 가장 오른쪽 아래이며, 각 칸에서는 상하좌우 칸이 나타내는 인접 지역으로만 이동할 수 있다. (표에 표시되지 않은 지역이나 대각선 방향으로는 이동 불가.) 인접 지역으로 이동시에는 기본적으로 1만큼의 연료가 들고, 더 높은 곳으로 이동하는 경우 높이 차이만큼 추가로 연료가 소비된다. 색이 칠해진 칸을 따라 이동하는 경우 기본적인 연료 소비량 4에, 높이가 0에서 1로 경우만큼 추가 연료가 소비되므로 최소 연료 소비량 5로 목적지에 도착할 수 있다. 이동 가능한 지역의 높이 정보에 따라 최소 연료 소비량을 출력하는 프로그램을 만드시오.

입력

첫 줄에 테스트 케이스의 개수 T가 주어지고, 테스트 케이스 별로 첫 줄에 표의 가로, 세로 칸수N, 다음 줄부터 N개 지역의 높이 H가 N개의 줄에 걸쳐 제공된다. 1<=T<=50, 3<=N<=100, 0<=H<1000

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 3 0 2 1 0 1 1 1 1 1 5 0 0 0 0 0 0 1 2 3 0 0 2 3 4 0 0 3 4 5 0 0 0 0 0 0 5 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1	#1 5 #2 8 #3 9

---

2. 문제풀이

저런 최소이동비용은 다익스트라 알고리즘을 이용하여 풀면 된다. 다익스트라는 모든지점을 무한대의 거리로 둔다음에 시작위치에서 이동비용을 계산하여 최소값을 갱신하며 나아가는 알고리즘이다. 각 지점의 최소값을 구해 갱신해 나가다보면 목표지점의 최소비용이 구해진다.

 

---

3. 소스코드

#D3 5250 최소 비용
from collections import deque
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
 
for t in range(int(input())):
    N = int(input())
    map_list = [list(map(int, input().split())) for _ in range(N)]
    INF = float('inf')
    #도착까지 드는 비용 표시
    distance = [[INF for _ in range(N)] for _ in range(N)]
    #처음 부분은 0으로 초기화
    distance[0][0] = 0
    #앞쪽부터 꺼낼꺼니까 디큐사용
    queue = deque()
    #시작점은 0,0
    queue.append((0, 0))
    #큐가 빌대까지 반복
    while queue:
        #좌표 꺼내고
        y, x = queue.popleft()
        #이동할 방향 선택해서
        for dy, dx in move:
            #이동해 봤을때
            my, mx = dy+y, dx+x
            #표에 벗어나지 않는다면
            if 0 <= my < N and 0 <= mx < N:
                #기본 이동비용1
                temp = 1
                #높이차만큼 추가해주고
                if map_list[my][mx] > map_list[y][x]:
                    temp += map_list[my][mx] - map_list[y][x]
                #거리 갱신해주고 큐에 추가
                if distance[my][mx] > distance[y][x] + temp:
                    distance[my][mx] = distance[y][x] + temp
                    queue.append((my, mx))
    #도착점까지의 거리 출력
    print('#{} {}'.format(t+1, distance[N-1][N-1]))