[BOJ, Python] 11404번_플로이드

백준 11404번

문제 난이도: 골드 4
혼자의 힘으로 풀었는가?: X

문제를 처음 봤을 때는 그래프 탐색 문제라고 생각했다.
그래서 단순히 bfs를 사용해서 문제를 풀어봤다.

그러나 한 가지 간과한 것이 있었는데 이 문제의 논점은 각 점으로 가는 최단 경로를 찾는 것이다. bfs는 가중치가 모두 동일한 경우에는 최단 경로를 보장하기 때문에 bfs는 해당 문제에 맞는 알고리즘이 아니다.

가중치가 존재하는 그래프 문제는 일반적으로 플로이드-워셜, 다익스트라, 벨만-포드 알고리즘 등을 사용해야 한다.

나는 플로이드-워셜, 다익스트라 알고리즘을 각각 사용해서 2번 풀었는데 각각의 시간 복잡도는 아래와 같다.

시간 복잡도

• 플로이드-워셜: O(n^3)
• 다익스트라: O((n+m)logn) (우선순위 큐를 사용한 경우)

둘 중 어떤 알고리즘을 사용하는지는 결정할 때는 n의 크기를 고려하면 된다.

n의 범위가 2<=n<=100 이기 때문에 유용성과 구현 편의성을 생각하면 플로이드-워셜 알고리즘이 유리할 수 있다.

플로이드-워셜 알고리즘 풀이

import sys
input = lambda: sys.stdin.readline().rstrip()
import heapq

INF = float('inf')

# 도시의 개수와 버스의 개수 입력
n = int(input())
m = int(input())

# 초기화: 모든 비용을 무한대로 설정
dist = [[INF] * n for _ in range(n)]

# 자기 자신으로 가는 비용은 0으로 설정
for i in range(n):
    dist[i][i] = 0

# 버스 정보 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = min(dist[a-1][b-1], c)  # 같은 노선에 대해 더 작은 비용 저장

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

for i in range(n):
    for j in range(n):
        if dist[i][j] == INF:
            print(0, end=" ")
        else:
            print(dist[i][j], end=" ")
    print()

플로이드-워셜 알고리즘을 사용한 구현은 간단하다.

1. 모든 쌍의 최단 경로를 계산한다.

# 초기화: 모든 비용을 무한대로 설정
dist = [[INF] * n for _ in range(n)]

# 자기 자신으로 가는 비용은 0으로 설정
for i in range(n):
    dist[i][i] = 0

# 버스 정보 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = min(dist[a-1][b-1], c)  # 같은 노선에 대해 더 작은 비용 저장
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

2. 존재하지 않는 경로는 0으로 변환하고 출력한다.

for i in range(n):
    for j in range(n):
        if dist[i][j] == INF:
            print(0, end=" ")
        else:
            print(dist[i][j], end=" ")
    print()

플로이드-워셜 알고리즘 결과

다익스트라 알고리즘 풀이

import sys
input = lambda: sys.stdin.readline().rstrip()
import heapq

## 다익스트라 알고리즘 풀이

def dijkstra(n, start):
    dist = [float("inf")]*n
    dist[start] = 0

    pq = [(0, start)] # 거리, 정점

    while pq:
        c_dist, u = heapq.heappop(pq)
        
        if c_dist > dist[u]: # 이미 처리됐다면 패스
            continue

        for v, w in graph[u]:
            distance = w + c_dist

            if dist[v] > distance:
                dist[v] = distance
                heapq.heappush(pq, (distance,v))
    return dist


# 도시의 개수와 버스의 개수 입력
n = int(input())
m = int(input())

graph = [[] for _ in range(n)]

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

for i in range(n):
    li = dijkstra(n, i)
    li = [0 if x == float("inf") else x for x in li]
    print(*li)

다익스트라 알고리즘의 기본 코드는 그래프 탐색과 유사하다. 한 가지 차이가 있다면 우선순위 큐를 사용한다는 것이다.
우선순위 큐를 사용하여 현재 가장 짧은 경로를 빠르게 찾을 수 있다.

1. 다익스트라 알고리즘

def dijkstra(n, start):
    dist = [float("inf")]*n
    dist[start] = 0

    pq = [(0, start)] # 거리, 정점

    while pq:
        c_dist, u = heapq.heappop(pq)
        
        if c_dist > dist[u]: # 이미 처리됐다면 패스
            continue

        for v, w in graph[u]:
            distance = w + c_dist

            if dist[v] > distance:
                dist[v] = distance
                heapq.heappush(pq, (distance,v))
    return dist

각 지점까지의 거리를 담을 dist 리스트를 만들어주고 초기값은 매우 큰 값float("inf")를 넣는다.
우선순위 큐를 사용해서 거리를 기준으로 push한다.

이때 현재 거리(c_dist)가 dist 현재 위치의 거리보다 크다면 이미 처리된 지점이기 때문에 패스해준다.

2. 다익스트라 알고리즘을 통과한 결과 중에서 float('inf')와 같은 값은 존재하지 않는 경로이기 때문에 0으로 변환한다.

for i in range(n):
    li = dijkstra(n, i)
    li = [0 if x == float("inf") else x for x in li]
    print(*li)

다익스트라 알고리즘 결과