https://leetcode.com/problems/network-delay-time/description/

📢다익스트라 알고리즘이 BFS+Priority Queue인 것은 알았지만, 그것보다 더 중요한 것을 간과했기 때문에 우선 "모든 노드를 라벨링한 이후에야 알고리즘을 종료"를 왜 해야하는지 다음 그래프를 보면서 분석해보자.

다익스트라의 원리

다음과 같은 그래프가 주어지고 시작점은 A, 도착점은 H라 하자.

알고리즘의 순서는 다음과 같다
1. 각각의 점에 라벨을 매겨 줄 것이다. 시작점의 라벨은 0으로 초기화하고, 나머지 점들은 ∞로 초기화 한다.
2. 사용 안 한 라벨 중 제일 작은 라벨을 찾고, 해당 라벨을 사용했다고 표시해준다.
3. 해당 점에 인접한 점들의 라벨들을 업데이트 해준다. (이미 라벨 되어 있는 값보다 작으면 그 값으로 업데이트 해주고, 크면 업데이트 하지 않는다.)
그리고 2~3의 과정을 반복한다.
4. 모든 라벨을 사용했으면 종료한다.

다익스트라의 진행

📢우리는 위의 알고리즘 순서를 하나씩 그림으로 살펴볼껀데, 그와 동시에 위의 순서가 이전 다익스트라 알고리즘에서 다뤘던 코드로 어떻게 구현됬는지도 살펴볼 것이다.

1. 시작 점 A 라벨은 0으로 초기화

• 💻우선순위 큐에 시작노드 추가

heapq.heappush(pq, (0, start))

2. 나머지 라벨은 ∞로 초기화

1. 사용 안 한 라벨 중에서 가장 작은 것은? => A(0)

• 💻우선순위가 가장 높은 노드 추출

while pq:
	cur_cost, cur_v = heapq.heappop(pq)

2. A(0) 사용 처리, A(0) 인접 점의 라벨 업데이트: B(∞) -> B(2), D(∞) -> D(1)

• 💻방문 여부 확인 & 현재 노드와 연결된 노드 우선순위 큐에 추가

if cur_v not in costs:
	costs[cur_v] = cur_cost
    for next_v, cost in graph[cur_v]:
    	next_cost = cur_cost + cost
        heapq.heappush(pq, (next_cost, next_v))

모든 라벨들이 업데이트 되었으므로, 알고리즘은 종료되고, costs에 추가한 것들 중 도착점의 최소 비용을 리턴하면 된다.

다시 문제로 돌아와서, 이전에 했던 3단계 절차를 적용해서 먼저 문제 해석 단계부터 해보자.

📜문제 해석

1~N까지 라벨링된 N개의 노드가 주어졌다.
times[i]={u, v, w}: u는 source node, v는 target node, 그리고 w는 신호가 source로부터 target까지 이동하는데 걸리는 시간
-> V=(u,v), E=w

우리는 k번 노드로부터 신호를 보낼 것이다. N개의 모든 노드가 신호를 받는데 걸리는 최소 시간을 리턴하라. 만약 모든 N개의 노드가 신호를 받는게 불가능하다면, -1을 리턴하라.
-> n: 총 노드 개수, k: 신호가 출발하는 노드 번호

나는 문제를 해석하는 과정 중에서 의문이 든 점을 chatgpt를 통해 다음과 같이 해결하였다.

Q&A

❓ N개의 모든 노드가 신호를 받는데 걸리는 최소 시간을 리턴하라?
❗ 다익스트라 알고리즘의 핵심은 우선순위 큐(min heap)를 통해 항상 현재까지의 최단 경로를 가진 노드를 선택하고, 그 노드로부터 인접 노드들을 탐색하면서 경로를 업데이트해 나가니까, 결국 모든 노드를 라벨링하게 되는데, 그 중 최단 경로를 리턴하라는 뜻

💡파라미터로 n개의 노드를 주었는데, Example 3에서 times = [[1,2,1]], n = 2, k = 2 케이스가 주어지고, 그에 대한 Output은 -1이다.
이게 무슨 의미냐면 G=(V=(1,2), E=1)로 그래프가 주어졌는데, 신호를 보내는 노드는 2번 노드라서 모든 2개의 노드가 신호를 받는게 불가능하기 때문에 -1을 리턴했다는 뜻이다.
(∵다익스트라 알고리즘은 Directed graph를 사용)

이 점을 고려하면, 기존의 다익스트라 템플릿 코드를 변형할 수 밖에 없다는 것을 알 수 있다.

⚙코드 설계

1. k번 노드로 부터 신호를 쏜다 -> 시작 노드를 추가할 때 heapq.heappush(pq, (0, k))
2. times는 2차원 배열

Q&A

❓ 마지막 조건의 "만약 모든 N개의 노드가 신호를 받는게 불가능하다면, -1을 리턴하라."을 어떻게 코드로 구현하지? & 방향이 다른 edge는 신호가 도달하지 못하니까 이것을 어떻게 -1로 리턴하게 만들지?
❗ 둘다 우선순위 큐가 비어있으면 그냥 -1을 리턴하면 됨. (∵방향이 다른 edge는 신호가 도달하지 못했다는 것은 결국 모든 N개의 노드가 신호를 받는게 불가능하다는 것과 같은 말)

💻코드 구현

class Solution(object):
    def networkDelayTime(self, times, n, k):
        costs = {}
        pq = []
        heapq.heappush(pq, (0, k))  # 시작 노드 추가

        while pq:
            cur_cost, cur_v = heapq.heappop(pq)
            if cur_v not in costs:
                costs[cur_v] = cur_cost
                if len(costs) == n: # 모든 노드를 방문했으면 최소 비용을 리턴
                    return cur_cost
                # 인접 노드 탐색(먼저 방문을 해야 탐색 시작)
                for path in times:  # path is row
                    if cur_v == path[0]:  # 시작 노드인지 확인
                        cost = path[2]
                        next_v = path[1]
                        next_cost = cur_cost + cost
                        heapq.heappush(pq, (next_cost, next_v))
        return -1 # 그렇지 않으면 -1을 리턴

        # for next_v, cost in graph[cur_v]:
        # next_cost = cur_cost + cost
        # heapq.heappush(pq, (next_cost, next_v))

위의 코드를 구현하는 과정 중에서 인접 리스트가 아닌, 2차원 배열의 times가 주어졌기 때문에 이것을 어떻게 코드 템플릿에 녹일지에 대해 무척 고민을 많이 했었는데 그냥 인덱싱해서 각각의 변수에 할당해주었다.

🧐참고로, 파이썬은 iterable한 객체(튜플, 리스트)의 원소들을 직접 변수에 할당이 가능하기 때문에 아래와 같이 코드를 작성할 수도 있다.

for v, next_v, cost in times:
    if v == cur_v:
        next_cost = cur_cost + cost
        heapq.heappush(pq, (next_cost, next_v))

📢참고로, 본인은 파이썬에서 자바로 코테 언어를 변경할 것인데, 자바에서는 위와 같은 언패킹 기능이 없으므로 스스로 짠 인덱싱 기법을 활용하자.