[프로그래머스] 배달(Dijkstra)

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

코딩테스트 연습 - 배달

 

다익스트라(Dijkstra)를 그대로 활용하는 문제입니다. 

문제부터 간단하게 요약하면, 

 

N개의 마을로 이루어진 나라에서 서로 양방향으로 이동이 가능하고 걸리는 시간이 주어지는 그래프가 주어질 때, 1번 마을이 주어진 시간 내에 배달할 수 있는 마을의 수를 return하는 문제입니다. 

위와 같은 상황에서 1번 마을이 3 이하의 시간으로 배달이 가능한 마을들은 [1,2,4,5]이고, 그래서 4를 return 하여야 합니다. 

 

결과적으로 solution(N, road, K)에

N : 마을의 개수

road : 마을을 연결하는 도로의 정보

K : 음식 배달이 가능한 시간

이 input으로 들어갈 때

 

1번 마을에서부터 K의 시간안에 배달 할 수 있는 마을의 갯수를 return하여야 합니다. 

 

<Solution>

이 문제의 아이디어는 Dijkstra 알고리즘을 활용하는 것입니다. 사실 문제의 상황조건이 굉장히 정확하게 이 알고리즘을 사용하여라고 제시하는 듯한 느낌입니다. 

(다익스트라 알고리즘에 관한 이야기는 추후 포스트에서 다루어 보도록 하겠습니다)

 

음의 간선이 존재하지 않고, 한 정점(특정 정점)으로 부터 갈 수 있는 다른 모든 정점들 까지의 최단 경로를 구하는 문제입니다. 이렇게 최단 경로를 구해서 array를 만들고 K보다 작거나 같은 것의 갯수를 count해주면 됩니다. 

 

주의 할 점은 문제의 조건에서 한 마을에서 다른 마을로 가는 road가 여러개 있을 수도 있다는 조건입니다. 1번과 2번 마을이 3시간이 걸리는 도로, 4시간이 걸리는 도로 등 여러 도로가 존재할 수 있다는 것입니다. 그래서 array를 만들어 줄 때 이러한 중복된 도로중 가장 시간이 적게 걸리는 도로를 반영해서 2D array를 구성하여야 합니다. 

 

실제 코드 구현은 아래와 같습니다. 

import copy
def solution(N, road, K):
    # build 2d road array
    array = [[int(2e9)] * N for _ in range(N)] # kind of infinite array

    for i in range(N):
        array[i][i] = 0

    # roads are connected bidirectional
    for road_ in road:
        if array[road_[0]-1][road_[1]-1] > road_[2]:
            array[road_[0]-1][road_[1]-1] = road_[2]
            array[road_[1]-1][road_[0]-1] = road_[2]

    # dijkstra
    visited = [False] * N
    visited[0] = True

    distance = copy.deepcopy(array[0])

    for i in range(N-2):
        # find smallest
        min_ = int(2e9)
        index = 0
        for j in range(N):
            if not visited[j] and distance[j] < min_:
                min_ = distance[j]
                index = j
        if index == 0: # no way 
            break

        visited[index] = True
        for k in range(N):
            if not visited[k]:
                if distance[index] + array[index][k] < distance[k]:
                    distance[k] = distance[index] + array[index][k]

    answer = 0

    for d in distance:
        if d <= K:
            answer += 1
    
    return answer