[Python] SW Expert Academy #1249 보급로

📚문제: #1249 보급로(D4)

전체 코드

# 1249. 보급로

from heapq import heappush, heappop

# 최소비용을 계산하는 함수
def min_cost(n, graph, t):
    
    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    # 시작노드 (비용, 좌표)
    s = (0, [0,0])
    
    # 우선순위 큐
    q = []
    heappush(q, s)
    
    # 큐가 빌 때까지 계속 반복
    while q:
        
        # 우선순위 큐에서 뽑는다.
        cost, coord = heappop(q)
        
        # 좌표
        cur_r, cur_c = coord
        
        # 마지막 지점 도착 시 답 출력 후 종료
        if cur_r == n-1 and cur_c == n-1:
            
            print("#{} {}".format(t, cost))
            return
        
        # 4방향 탐색
        for i in range(4):
            
            move_r, move_c = cur_r + dr[i], cur_c + dc[i]

            # 주어진 영역을 벗어나지 않으면서
            if 0 <= move_r <= n-1 and 0 <= move_c <= n-1:
                
                # 아직 방문되지 않은 노드일 때
                if graph[move_r][move_c] != 'v':
                    
                    add = (cost+graph[move_r][move_c], [move_r, move_c])
                    
                    # 우선순위 큐에 추가
                    heappush(q, add)

                    # 방문처리
                    graph[move_r][move_c] = 'v'            
                
# 전체 테스트케이스 수
T = int(input())

# 테스트 케이스
for t in range(1, 10+1):
    
    # 지도의 크기
    N = int(input())
    
    # 지도
    grid = []
    
    for _ in range(N):
        
        grid.append(list(map(int, input().rstrip())))
    
    # 함수 실행
    min_cost(N, grid, t)

아이디어

너비우선탐색(BFS)와 우선순위 큐(Priority Queue)의 개념 적용, 이동할 수 있는 이웃좌표에 대해서 비용이 적은 순서대로 큐에 넣는다.