[SWEA/Python] 5250. 최소 비용

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. bfs를 활용해서 인접한 지역으로 이동한다.
2. 이동한 지역이 이동 전 지역보다 높을 경우, 차이를 저장해준다.
3. 이동할 지역에 이미 저장된 비용보다 현재의 경로로 이동할 때의 비용이 더 덜든 다면, 비용을 갱신해준다.
   (이 조건이 있기 때문에 따로 방문체크를 안해줘도 된다! 방문체크를 하면 오히려 최소 거리로만 이동하게 된다.)

 

📌 코드

from collections import deque
import sys
sys.stdin = open('input.txt')

def bfs(i, j):
    distance[i][j] = 0

    queue = deque()
    queue.append((i, j))

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

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

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

                if distance[x][y] + 1 + diff < distance[nx][ny]:
                    distance[nx][ny] = distance[x][y] + 1 + diff
                    queue.append((nx, ny))

    return distance[N-1][N-1]


T = int(input())

for t in range(1, T+1):
    N = int(input())
    region = [list(map(int, input().split())) for _ in range(N)]

    distance = [[float('inf') for _ in range(N)] for _ in range(N)]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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