[SW Expert Academy] 5249. 최소 비용

5249. 최소 비용

---

문제)

 

출발에서 최종 도착지까지 경유하는 지역의 높이 차이에 따라 연료 소비량이 달라지기 때문에, 최적의 경로로 이동하면 최소한의 연료로 이동할 수 있다.

다음은 각 지역의 높이를 기록한 표의 예로, 항상 출발은 맨 왼쪽 위, 도착지는 가장 오른쪽 아래이며, 각 칸에서는 상하좌우 칸이 나타내는 인접 지역으로만 이동할 수 있다.

(표에 표시되지 않은 지역이나 대각선 방향으로는 이동 불가.)

 

 

인접 지역으로 이동시에는 기본적으로 1만큼의 연료가 들고, 더 높은 곳으로 이동하는 경우 높이 차이만큼 추가로 연료가 소비된다.

 

 

 

색이 칠해진 칸을 따라 이동하는 경우 기본적인 연료 소비량 4에, 높이가 0에서 1로 경우만큼 추가 연료가 소비되므로 최소 연료 소비량 5로 목적지에 도착할 수 있다.

이동 가능한 지역의 높이 정보에 따라 최소 연료 소비량을 출력하는 프로그램을 만드시오.

 

 

[입력]

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

1<=T<=50, 3<=N<=100, 0<=H<1000

 

 

[출력]

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

 

 

 

 

풀이)

 

 

from collections import deque
 
# 지역을 벗어나지 않도록
def in_range(x, y):
    return -1 < x < n and -1 < y < n
 
def bfs(a, b):
 
    queue = deque()
    queue.append([a, b])
    # 어짜피 출발지역은 보지 않을 것이므로 이상하게 나와도 된다.
    visited[a][b] = 0
 
    while queue:
        a, b = queue.popleft()
 
        for i in range(4):
            x = a + di[i]
            y = b + dj[i]
            if not in_range(x, y):
                continue
            
            # 아직 방문을 한번도 하지 않았을 경우
            if visited[x][y] == 0:
                visited[x][y] = visited[a][b] + 1 + max(g[x][y] - g[a][b], 0)
                queue.append([x, y])
 
            # 다시 방문했을 때, 더 최소비용이라면 갱신
            # max(g[x][y] - g[a][b], 0) ==> 내려가는 길이라면, 0이 더해지도록
            elif visited[a][b] + max(g[x][y] - g[a][b], 0) + 1 < visited[x][y]:
                visited[x][y] = visited[a][b] + max(g[x][y] - g[a][b], 0) + 1
                queue.append([x, y])
 
 
T = int(input())
for _ in range(T):
    n = int(input())
    g = [list(map(int, input().split())) for i in range(n)]
    visited = [[0] * n for i in range(n)]
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
    # 0, 0 에서 출발
    bfs(0, 0)
    print(f"#{_ + 1} {visited[n - 1][n - 1]}")
 

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.