🏀 개요

최단 경로 탐색에 대해서 알아보고자 한다.

참고 :
동빈나 유튜브 채널을 기반으로 정리한 것으로, 유튜브 링크를 첨부 하겠습니다.
동빈나 유튜브 링크

💡 접근 방식

케이스가 다양한 경우가 있다.

한 지점에서 다른 한 지점이나, 다른 모든 지점에 대한 최단 경로 찾기 -> 다익스트라

모든 지점에서 다른 모든 지점에 대한 최단 경로 찾기 -> 폴로이드 워셜

💎 다익스트라

결국 그리디 알고리즘을 기반으로 최단 경로를 탐색하는 것이다.

방문하지 않은 노드 중 최단 경로를 방문함으로서 최단 경로 테이블을 꾸준히 업데이트 한다.

이게 가능한 이유는 한 번 방문된 노드의 최단 거리가 고정된다는 특징이 있어서 인데, 실제로 그래프를 탐색해보면 이것이 옳다는 것을 알 수 있다.

순서:

출발 노드 설정 -> 최단 거리 테이블 초기화 -> 방문 x, 최단 거리 노드 -> min(해당 노드를 거쳐서 다른 노드로 가는 비용, 현재 최단 거리 테이블)

출발 노드는 거리가 0 으로 초기화 하고, 그 외 노드는 INF로 초기화 한다.(어떠한 경우에도 변경 가능할 수 있도록)

방문 x, 최단 거리 노드를 찾기 위해서 heap 기반의 우선순위 큐를 사용 한다. 거리 기준으로 min heap을 생성 한다면, 쉽게 최단 거리 노드를 얻을 수 있다.

#초기화

# 그래프
graph = [[] for i in range(n + 1)]

# 최단 거리
INF = int(1e9)
distance = [INF] * (n + 1)

# 간선 정보

for _ in range(m):
	a,b,c = map(int,input().split())
    graph[a].append(b,c) # b 노드로 c 거리

# 최단 경로 탐색

def dijkstra(start):
	q = []
    import heapq
    heapq.heappush(q,(0,start)) # 거리, 노드
    distance[start] = 0
    while q:
    	# 최단 거리 노드 얻기
        dist, now = heapq.heappop(q)
        
        # 이미 처리된 적이 있다면 무시
        if distance[now] < dist:
        	continue
        else:
        	for i in graph[now]: # 인접노드
            	cost = dist + i[1]
                if cost < distance[i[0]]:
                	distance[i[0]] = cost # 최단거리 변경
                    heapq.heappush(q,(cost,i[0])) # heap 내용도 변경

이런식으로 코드가 작성 가능하다.

💎 플로이드 워셜

이차원 테이블을 통해 방향성과 cost를 보여주고, 이를 기반으로 DP 방식으로 최단 거리 탐색

점화식 Dab = min(Dab, Dak + Dkb) # 기존 최단 거리와 거쳐서 가는 케이스를 비교하여 최소값을 저장

# 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
	for b in range(1, n + 1):
    	if a == b:
        	graph[a][b] = 0

for _ in range(m):
	a,b,c = map(int,input().split())
    graph[a][b] = c
   
# 최단 경로 탐색
for k in range(1, n + 1):
	for a in range(1, n + 1):
    	for b in range(1, n + 1):
        	graph[a][b] = min(graph[a][b],graph[a][k] + graph[k][b])

보는 것과 같이 복잡도에서는 O(n^3) 의 방식으로 단점이다. 수가 적을 때만 가능하다.

🔧 예제 문제

전보 (다익스트라 예시, 유튜브를 통해서 설명 참고)

미래도시(플로이드 워셜 예시, 유튜브를 통해서 설명 참고)