[SWEA 5250번] 최소 비용 - 파이썬(python)

SW Expert Academy

문제

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

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

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

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

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

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

입력

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

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

출력

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

풀이

• 처음에는 항상 BFS를 풀던 방식으로 방문 여부를 체크하면서 큐에 최소비용을 갱신하면서 풀이했다.
• 그러다보니 높이에 따른 가중치로 인해 돌아가는 것이 최소비용이 되는 경우를 계산하지 못했다.
• 따라서 현재지점에서의 최소비용을 저장할 cost배열을 만들어 모든 경우를 탐색하면서 최소비용을 저장했다.
• 모두 탐색한 이후에는 (N-1,N-1)지점의 값을 출력한다.

코드

from collections import deque

def bfs(y,x):
    q=deque()
    q.append([y,x])
    while q:
        ny,nx = q.popleft()
        for i in range(4):
            dy=ny + directy[i]
            dx=nx + directx[i]
            if 0<=dy<N and 0<=dx<N:
                # 현재 높이보다 높다면 (이동할 곳 높이-현재높이)+1이 비용에 추가되어야 한다.
                # 비교후 최소비용 갱신
                if arr[dy][dx] > arr[ny][nx]:
                    if cost[dy][dx] > (cost[ny][nx]+arr[dy][dx]-arr[ny][nx]+1):
                        cost[dy][dx] = (cost[ny][nx] + arr[dy][dx] - arr[ny][nx] + 1)
                        q.append([dy,dx])
                # 현재 높이보다 낮거나 같다면 기본 연료 1을 더해준다.
                else:
                    if cost[dy][dx] > cost[ny][nx]+1:
                        cost[dy][dx] = cost[ny][nx] + 1
                        q.append([dy, dx])


T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    # 최소비용을 갱신하기 위한 배열
    # 방문 배열 사용시 돌아가는 것이 더 적은 비용이 들더라도
    # 이미 방문한 곳에는 갈 수 없어 최소비용을 구하지 못하는 문제가 발생한다.
    cost = [[int(21e8)]*N for _ in range(N)]
    directy = [1,-1,0,0]
    directx = [0,0,1,-1]
    # 출발지점 비용 0으로 설정
    cost[0][0]=0
    bfs(0,0)
    print(f'#{test_case} {cost[N-1][N-1]}')