[코테 알고리즘] 최단 경로 / 관련 문제

본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련된 문제들을 찾아 정리하였습니다.

시리즈 보기
[코테 알고리즘] 파이썬 기본 / 관련 문제
[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제
[코테 알고리즘] 그리디 / 관련 문제
[코테 알고리즘] 구현 / 관련 문제
[코테 알고리즘] DFS, BFS / 관련 문제
[코테 알고리즘] 정렬 / 관련 문제
[코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제
[코테 알고리즘] 최단 경로 / 관련 문제
[코테 알고리즘] 그래프 이론 / 관련 문제

 

최단 경로

• 가장 짧은 경로를 찾는 알고리즘
• = 길 찾기 알고리즘
• 다양한 유형
  • 한 지점에서 다른 특정 지점까지의 최단 경로 구하기
  • 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하기
• 그래프를 이용해 표현
• 최단 거리 알고리즘
  • 다익스트라 최단 경로 알고리즘
  • 플로이드 워셜
  • 벨만포드 알고리즘

 

다익스트라 최단 경로 알고리즘

• 특정한 노드에서 출발하여 다른 노드로 가는 최단의 경로를 구하는 알고리즘
  • = 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우
• 기본적으로 그리디로 분류
  • 매번 가장 비용이 적은 노드를 선택해 임의의 과정 반복
  • 각 노드에 대한 현재까지의 최단 거리 정보를 저장하며 계속 갱신
• 알고리즘 원리
  1. 출발 노드 설정
  2. 최단 거리 테이블 초기화
  3. 방문하지 않은 노드 중 최단 거리가 짧은 노드를 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

 

방법 1. 간단한 다익스트라 알고리즘

• O(V^2)의 시간 복잡도
• 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 방문하기 위해
  • 매 단계마다 1차원 리스트의 모든 원소를 확인

 

방법 2. 개선된 다익스트라 알고리즘

• O(ElogV) 보장
• 힙 자료 구조를 사용
  • 특정 노드까지의 최단 거리에 대한 정보를 힙에 담어서 처리
  • 출발 노드부터 가장 거리가 짧은 노드를 더욱 빠르게 찾음
  • 다익스트라 최단 경로 알고리즘은 비용이 적은 노드를 우선 방문
    • 최소 힙 구조를 기반으로 하는 파이썬 우선 순위 큐 라이브러리 사용
• 우선순위 큐를 적용하여 다익스트라 최단 경로 알고리즘 설계
  • 최단 거리를 저장하기 위한 1차원 리스트는 동일
  • 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가적으로 사용

import sys
input = sys.stdin.readline
import heapq
INF = int(1e9)

# 노드의 개수, 간선의 개수
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

# 모든 간선의 정보 입력
for _ in range(m):
    # a번 노드에서 b번 노드로 가는 비용이 c
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heappush(q, (0, start))
    distance[start] = 0
    while q: 
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
		    heapq.heappush(q, (0, start))
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드를 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

 

문제

특정 거리의 도시 찾기

18352번: 특정 거리의 도시 찾기

import sys
input = sys.stdin.readline
import heapq
INF = int(1e9)

n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append((b, 1))

def dikstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dikstra(x)
can = False
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        can = True
if not can:
    print(-1)

 

BFS 로 풀기

import sys
input = sys.stdin.readline
from collections import deque

n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n + 1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

def bfs(start):
    que = deque()
    que.append((start, 0))
    visited[start] = True
    answer = []

    while que:
        now, dist = que.popleft()
        if dist == k:
            answer.append(now)
            continue
        for i in graph[now]:
            if not visited[i]:
                que.append((i, dist + 1))
                visited[i] = True
    return answer

answer = bfs(x)
answer.sort()
if answer:
    for a in answer:
        print(a)
else:
    print(-1)

 

숨바꼭질 - 다익스트라

13549번: 숨바꼭질 3

import heapq
INF = int(1e9)

N, K = map(int, input().split())  # 시작 위치, 도착 위치
distance = [INF]*100001  # 100001개의 떨어진 거리

def dijkstra(start):  # 다익스트라
    distance[start] = 0  # 시작 위치 초기화
    q = []
    heapq.heappush(q, (0, start))  # 시작 위치 우선 순위 큐 삽입

    while q:  # q에 값이 있을 동안
        dist, now = heapq.heappop(q)  # 거리가 가장 짧은 노드
        if distance[now] < dist:
            continue
        for a, b in [(now*2, dist), (now+1, dist+1), (now-1, dist+1)]:  # 2배, 오른쪽, 왼쪽
            if 0 <= a <= 100000 and distance[a] > b:  # 범위 안에 있고 방문하지 않았다면(범위 주의)
                distance[a] = b
                heapq.heappush(q, (b, a))

dijkstra(N)  # 시작 위치 다익스트라 실행
print(distance[K])  # 시작 위치로부터 K가 떨어진 최소 거리

 

플로이드 워셜 알고리즘

• 모든 지점에서 다른 지점까지의 최단 경로를 모두 구해야하는 경우
• O(N^3)의 시간 복잡도

 

플로이드 워셜 알고리즘 vs 다익스트라 최단 경로 알고리즘

• 다익스트라 최단 경로 알고리즘
  • 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우
• 공통
  • 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행
• 차이점
  • 다익스트라 최단 경로 알고리즘
    • 그리디 알고리즘
  • 플로이드 워셜 알고리즘
    • 매번 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾을 필요가 없다는 점이 다름
    • 2차원 리스트에 최단 거리 정보를 저장
      • 모든 노드에 대해 다른 모든 노드로 가는 최단 거리 정보를 담음
    • 다이나믹 프로그래밍

 

수행

• 현재 확인하고 있는 노드를 제외, N-1개의 노드 중 서로 다른 노드 (A, B)쌍을 선택
  • 비용을 확인한 후 최단 거리를 갱신
• 3중 반복문을 이용하여 최단 거리 테이블을 갱신
  • $D_{ab} = min(D_{ab},~D_{ak} + D_{kb})$
    • A에서 B로 가는 최소비용
    • A에서 K를 거쳐 B로 가는 비용
    • 둘을 비교하여 더 작은 값으로 갱신

INF = int(1e9)

# 노드의 개수, 간선의 수
n, m = map(int, input().split())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에게 자기 자신으로 가는 비용은 0으로 초기화
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라고 설정
    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])
            
# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우 무한으로 출력
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()

 

문제

경로 찾기

11403번: 경로 찾기

import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(n):
        for k in range(n):
            if graph[j][i] and graph[i][k]:
                graph[j][k] = 1

for g in graph:
    print(*g)