[PROGRAMMERS] Summer/Winter : 배달 Python

이 문제는 한 마을에서 다른 마을로 이동할 때 비용(시간)이 주어질 때 다른 마을까지의 비용이 주어진 K보다 작은 마을의 개수를 구하는 문제이다.

가장 먼저 다익스트라가 떠올랐고 실제로 다익스트라 알고리즘을 통해 문제를 풀었다.

한가지 특이점은 보통 다익스트라는 목적지까지의 최소비용을 구할 때 많이 사용해온 알고리즘이지만 이 문제는 특별한 목적지가 존재하지 않다.

그렇기 때문에 나는 이 문제에서 heap 자료구조를 사용하지 않았다. 최소비용으로 갈 수 있는 경우에만 enqueue를 하면서 그래프 탐색을 하다가 더 이상 최소비용으로 갈 수 있는 도시가 없을 때 종료하도록 코드를 만들었다. (지금 생각해보니 heap을 사용하여 현재까지 비용이 K가 넘어가면 중지하는 식으로 구현해도 될 것 같다.)

정리하자면 나는 다익스트라를 통해 모든 도시를 최소비용으로가는 코드를 구현하여 그 최소비용이 K 이하인 마을의 개수를 세는 코드를 구현하였다. 이를 코드로 나타내면 아래와 같다. 

import math
from collections import deque

def solution(N, road, K):
    def dik(s):
        D[s] = 0
        Q = deque([[s,0]])

        while Q:
            nr, nc = Q.popleft()

            for c in R[nr]:
                cost = nc + c[1]
                if D[c[0]] > cost:
                    D[c[0]] = cost
                    Q.append([c[0],cost])

    D = [math.inf] * (N+1)
    R = [[] for _ in range(N+1)]


    for s,e,w in road:
        R[s].append([e,w])
        R[e].append([s,w])
    dik(1)


    return sum([1 if D[i] <=K else 0 for i in range(1,N+1)])

 방향성이 없기 때문에 R(경로변수)에  시작점과 끝점을 바꿔가면서 저장을 하였고, 다익스트라 코드에서는 최솟값으로 새로운 노드로 갈 때만 enqueue하였다.