Python - [프로그래머스]12978-배달

출처

https://school.programmers.co.kr/learn/courses/30/lessons/12978

문제

1번 마을부터 다른 모든 마을까지의 최단거리를 구한 후, K보다 작은 거리인 마을의 갯수를 구하는 문제이다.

접근 방법

이 문제는 Dijkstra 알고리즘을 사용하여 해결하는 문제이다.
Dijkstra 알고리즘은 DP를 활용하여 최단경로를 탐색하는 대표적인 문제이다. 이 알고리즘은 특정 하나의 정점에서 다른 모든 정점으로 가는 최단거리를 알려주는 알고리즘이다.

다익스트라 알고리즘이 DP인 이유는 최단거리는 여러 개의 최단거리로 이루어져 있기 때문이다. DP를 사용하는 조건인 작은 부분문제가 큰 문제에 속해있는 조건을 만족한다.

이 문제의 경우 1번 마을로 부터 다른 모든 마을로 가는 정점의 거리를 구한 후, 그 갯수를 구하면 되는 문제이다.

풀이

먼저, 간선의 정보를 받아와 그래프를 완성시켜 준 후, DP배열을 선언한다. 이후 DP에 기록을 하며 각각의 최단거리를 업데이트 해준다.

다익스트라에 대한 설명은 https://m.blog.naver.com/ndb796/221234424646 를 참조.

import sys
def solution(N, road, K):
    answer = 0
    road.sort()
    INF = sys.maxsize
    graph = [[INF]*(N+1) for _ in range(N+1)]
    visited = [0] * (N+1)
    for i in road:
        graph[i[0]][i[1]] = min(i[2], graph[i[0]][i[1]])
        graph[i[1]][i[0]] = min(i[2], graph[i[1]][i[0]])
    dp = [0]*(N+1)
    for i in range(N+1):
        dp[i] = graph[1][i]
    def get_min():
        m = INF
        idx = 0
        for i in range(1, N+1):
            if dp[i] < m and i not in visited:
                m = dp[i]
                idx = i
        return idx
    def dijkstra(start):
        visited.append(start)
        for i in range(N-1):
            now = get_min()
            visited.append(now)
            for j in range(1, N+1):
                if j not in visited:
                    dp[j] = min(dp[now] + graph[now][j], dp[j])
    dijkstra(1)
    for i in dp:
        if i <= K:
            answer +=1

    return answer + 1