Review 3 - 다익스트라/벨만-포드/플로이드-워셜/최소 신장 트리

4. 다익스트라

① 정의

• 특정 노드로부터 다른 모드까지의 최단 거리를 구하는 One-to-Many 알고리즘이다.

② 특징

• 모든 간선의 가중치는 0보다 크거나 같아야 한다.
• 유향 그래프, 무향 그래프, 사이클을 포함하는 그래프에서 모두 사용할 수 있다.

③ 구현에 사용되는 자료구조

• 그래프 표현을 위한 인접 리스트
• 최단 거리 리스트
• visited 배열
• Priority Queue

④ 아이디어

• 인접 리스트를 이용하여 그래프를 표현한다. 이 때, 인접 리스트에는 노드 번호와 가중치를 함께 저장해야 한다.
• 출발 노드를 기준으로 자기 자신까지의 거리는 0으로, 다른 모든 노드로의 거리는 ∞으로 초기화 된 최단 거리 리스트를 생성한다.
• 최단 거리 리스트에서 아직 방문하지 않은 노드 중 가장 작은 값을 갖는 노드를 선택한다.
• 선택된 노드로부터 다른 모든 노드에 이르는 Direct 경로 값과 기존 값 중 더 작은 값으로 최단 거리 리스트를 업데이트한다.
• 모든 노드를 방문할 때까지 위 과정을 반복한다.

⑤ 코드

def dijkstra(start):
    pq = PriorityQueue()
    pq.put((0, start))

    while not pq.empty():
        node = pq.get() # 가중치가 가장 작은 튜플(가중치, 노드 번호)을 가져옴.
        num = node[1] # 노드 번호

        if visited[num] == 0: 
            visited[num] = 1

            for temp in graph[num]:
                weight = temp[0]
                next = temp[1]
                dist[next] = min(dist[next], dist[num] + weight)
                pq.put((dist[next], next)) # 가중치가 우선 순위의 기준이 됨.

⑥ 주의 사항

• 출발 도시의 거리를 0으로 초기화하는 일을 잊어버리지 않도록 주의한다.

dist = [sys.maxsize] * (N + 1) 
dist[start] = 0

• PriorityQueue에 노드를 삽입할 때, 가중치 → 노드 번호 순서로 삽입하므로, 인접 리스트에 노드를 삽입할 때에도 가중치 → 노드 번호 순서로 저장하는 것이 좋다.

u, v, w = map(int, input().split()) # u, v는 정점, w는 가중치를 의미
graph[u].append((w, v)) # graph[u].append(w, v)로 쓰지 않도록 주의
pq.put((0, start)) # pq.put(0, start)로 쓰지 않도록 주의

• PriorityQueue에는 가중치가 최적이 아닌 튜플도 삽입되므로, 이미 방문한 노드에 대해서는 아무런 로직도 수행하지 않는다.
• PriorityQueue는 비어있는 상태도 True로 간주되므로, while pq:와 같은 조건식으로 작성할 경우 무한 루프에 빠지게 된다.

5. 벨만-포드

① 특징

• 다익스트라와 마찬가지로, 특정 노드로부터 다른 모드까지의 최단 거리를 구하는 One-to-Many 알고리즘이다.
• 가중치가 음수인 간선이 존재하는 그래프에서도 동작한다.
• 음수 사이클의 존재 여부를 감지하여, 최단 경로가 무한히 작은 값을 갖게 되는 현상을 방지한다.

② 아이디어

• 간선 리스트를 이용하여 그래프를 표현한다. 이 때, 간선 리스트에는 [출발, 도착, 가중치] 정보가 모두 저장되어야 한다.
• 출발 노드를 기준으로 자기 자신까지의 거리는 0으로, 다른 모든 노드로의 거리는 ∞으로 초기화 된 최단 거리 리스트(D)를 생성한다.
• 노드의 개수를 N이라 할 때, 간선 리스트 순회를 (N-1)번 반복하며 최단 거리 리스트를 업데이트한다.
  • 음수 사이클이 없다고 가정할 때, 최단 경로를 구성하귀 위해 필요한 간선의 수는 (N-1)을 넘을 수 없다.
  • u까지 갈 수 있는 경로가 존재하면서 D[v]의 기존 값보다 u를 거쳐 v로 가는 경로가 더 짧은 경우, 업데이트를 진행한다.
• 간선 리스트를 한번 더 순회하여 음수 사이클을 감지할 수 있다.

③ 벨만-포드의 단서

• 음수 가중치를 갖는 간선이 존재한다.
• 사이클 존재 여부를 감지해야 한다.

④ 핵심 포인트

• 벨만-포드는 간선 중심 알고리즘이므로, 간선 리스트를 사용한다.
• if D[u] != sys.maxsize and D[v] > D[u] + w: 조건식이 최단 거리 리스트 업데이트와 음수 사이클 감지에 모두 사용된다.
• 가중치가 항상 양수이더라도 사이클 감지가 필요하다면, 다익스트라가 아닌 벨만-포드로 풀이해야 한다.

6. 플로이드-워셜

① 정의

• 모든 노드 쌍에 대해 최단 거리를 구하는 Many-to-Many 알고리즘이다.

② 특징

• 가중치가 음수인 간선이 존재하는 그래프에서도 사용할 수 있다. 단, 음수 사이클이 존재하는 경우에 대해서는 적용할 수 없다. (음수 사이클 존재 시, 벨만-포드 알고리즘을 사용해야 한다.)
• 최단 거리를 구하기 위해 2차원 배열과 동적 계획법을 사용한다.
• 시간 복잡도가 매우 높기 때문에, 플로이드-워셜 알고리즘을 요구하는 문제는 노드 개수의 범위가 매우 적을 수 밖에 없다.

③ 아이디어

• 최단 거리 행렬에서 출발 노드(행 번호)와 도착 노드(열 번호)가 동일한 칸은 0으로, 나머지는 ∞으로 초기화한다.
• 최단 거리 행렬을 이용하여 그래프를 표현한다.
• 3중 for문의 형태로 최단 거리 행렬의 값을 업데이트한다.

for k in range(1, N + 1): # 중간 노드
	for i in range(1, N + 1): # 출발 노드
    	for j in range(1, N + 1): # 도착 노드
        	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

7. 최소 신장 트리

① 정의

• N개의 노드를 N-1개의 간선으로 연결하면서, 간선 가중치의 합이 최소가 되는 트리

② 특징

• 최소 가중치를 갖는 간선을 우선 선택하는 Greedy 기반 알고리즘이다.
• 사이클 형성 여부를 확인하기 위해 Union Find 알고리즘을 사용한다.
• 간선 리스트를 이용해 그래프를 표현한다.

③ 아이디어

• 간선 리스트와 Union Find 리스트를 초기화한다.
• Priority Queue를 사용하여 최소 가중치 간선을 선택하되, 이 때 사이클이 형성되지 않아야 한다.
• 사이클을 확인하는 방법은 아래와 같다.
  • 출발 노드(S)와 도착 노드(E)의 대표 노드를 찾는다.
  • S와 E의 대표 노드가 동일하지 않은 경우에만, Union 연산을 수행한다.
• 위 과정을 (N-1)번 반복하면서, 그 때마다 선택된 간선의 가중치를 더해나간다. 반복이 끝났을 때, 가중치의 총합이 곧 최소 신장 트리의 가중치가 된다.

④ (N - 1)번 반복하기

• 사이클 형성으로 인해 union 되지 않는 경우가 존재하므로, for 문을 (N - 1)번 반복하는 방식 대신 while 문을 사용해야 한다.
• while 문을 N번 반복하는 방법은 아래와 같다.
  • 반복 변수는 0으로 초기화하고, 등호 없는 부등호로 N과 대소를 비교한다.
  • 반복 변수를 1로 초기화하고, 등호 있는 부등호로 N과 대소를 비교한다.

cnt = 0 # 반복 변수를 0으로 초기화
result = 0 # 최소 신장 트리의 가중치

while cnt < (N - 1): # (N - 1)번 반복
    w, u, v = pq.get()
    if not isSameSet(u, v):
        union(u, v)
        cnt += 1
        result += w

⑤ 문제의 입력이 행렬 형태인 경우

• 이러한 문제에서도 인접 행렬 없이, 간선 정보만 추출하여 Priority Queue에 삽입한다.

## 문제의 입력 ##
3
abc
def
ghi
## 문제의 입력 ##

for i in range(N):
    temp = list(input().strip())
    for j in range(N):
    	# ord() 메서드를 통해 문자를 ASCII Code로 변환 
        if 'a' <= temp[j] <= 'z':
            w = ord(temp[j]) - ord('a') + 1
        elif 'A' <= temp[j] <= 'Z':
            w = ord(temp[j]) - ord('A') + 27
        else: # 간선이 없는 경우
            w = 0

        if i != j and w != 0: # 서로 다른 두 노드에 대해 간선이 존재하는 경우
            pq.put((w, i, j))

⑥ 신장 트리가 형성되지 않을 수도 있는 경우

• 신장 트리가 만들어지지 않는 경우, (N - 1)개의 간선을 사이클 형성 없이 연결할 수 없다. 그러므로 종료 조건을 while cnt < (N - 1)로 설정하면, 무한 루프에 빠지게 된다.
• 따라서 종료 조건을 while not pq.empty()로 변경하고, 사용한 간선의 개수를 통해 최소 신장 트리의 형성 여부를 판별해야 한다.

while not pq.empty():
    w, u, v = pq.get()
    
    if not isSameSet(u, v):
        union(u, v)
        cnt += 1
        result += w

if cnt == (N - 1):
    print(result)
else:
    print(-1)