[BAEKJOON] 11404 플로이드

https://www.acmicpc.net/problem/11404

11404번: 플로이드

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

---

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

---

풀이

처음엔 Dijkstra를 적용해서 풀어봤다. 내가 알고있는 알고리즘 중 가장 적합한 알고리즘이라 생각했다.

 

로직 : 다익스트라 Dijkstra

1. 정점 정보를 받아 그래프를 만든다
2. for문으로 모든 정점에 대한 Dijkstra 실행 후 결과값을 받아 출력

 

# 초기 코드 : 다익스트라
from collections import defaultdict
from sys import stdin
import heapq
input = stdin.readline

def dijkstra(n, start, bus_info):
    fringe = []
    heapq.heappush(fringe, (0, start))
    min_costs = [float("inf")] * (n + 1)
    min_costs[start] = 0

    while fringe:
        distance, current_city = heapq.heappop(fringe)

        if min_costs[current_city] < distance:
            continue

        for next_city, cost in bus_info[current_city]:
            new_distance = distance + cost

            if new_distance < min_costs[next_city]:
                min_costs[next_city] = new_distance
                heapq.heappush(fringe, (new_distance, next_city))

    min_costs = ['0' if i == float('inf') else str(i) for i in min_costs[1:]]
    return min_costs

n = int(input())
m = int(input())
bus_info = defaultdict(list)

for _ in range(m):
    start, end, cost = map(int, input().split())
    bus_info[start].append((end, cost))

for city in range(1, n + 1):
    min_costs = dijkstra(n, city, bus_info)
    print(' '.join(min_costs))
# 44012KB, 1180ms, 987B

 

기존의 다익스트라에서 문제 조건에 맞게 일부 수정해 제출했다.

결과는 성공. 하지만 다른 제출자들과 비교해보니 속도가 꽤 느렸다.

코드를 다시 확인해도 다익스트라 로직상 더 줄일만한 부분이 보이지 않았다.

한가지 예상되는 부분이 있다면 다익스트라 결과를 한번 더 정리하는 `result` 정도?

시간복잡도가 O(n)이라 가능성 있어보였지만 문제를 풀기위해 무조건 필요한 부분이라 생각했다.

약간의 검색을 해보니 플로이드 알고리즘이 따로 존재했다

.

플로이드 floyd 알고리즘은 모든 정점 간의 최단경로를 찾는 데 사용된다.
특히 모든 쌍의 최단 경로를 찾는 데 적합하다.

 

 

로직 : 플로이드 floyd

1. n개의 도시에 대한 2차원 배열을 생성하고, 이 배열을 무한대로 초기화
2. 배열의 대각선. 즉, 같은 도시로의 이동 비용은 0으로 설정
3. 입력으로 주어진 각 버스 노선에 대해, 배열을 업데이트하여 시작 도시와 도착 도시 간의 비용을 저장
4. 플로이드 알고리즘을 사용해 모든 쌍의 최소 비용을 계산
5. 계산된 최소 비용을 출력, 도시 i 에서 j 로 갈 수 없는 경우, 해당 위치에서는 0을 출력

# 1차 수정 : 플로이드
from collections import defaultdict
from sys import stdin
input = stdin.readline

def floyd(n, bus_info):
    inf = float('inf')
    dist = [[inf if i != j else 0 for j in range(n)] for i in range(n)]

    for start, end, cost in bus_info:
        start, end = start - 1, end - 1
        if dist[start][end] > cost:
            dist[start][end] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    for i in range(n):
        for j in range(n):
            if dist[i][j] == inf:
                dist[i][j] = 0

    return dist

n = int(input())
m = int(input())
bus_info = [tuple(map(int, input().split())) for _ in range(m)]

min_costs = floyd(n, bus_info)
for row in min_costs:
    print(' '.join(map(str, row)))
# 42212KB, 444ms, 824B

 

다익스트라와 플로이드를 비교해보면 다음과 같다

 

다익스트라와 플로이드 비교

	다익스트라	플로이드
목적	하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는다.	모든 정점 쌍 간의 최단 경로를 찾는다.
방식	탐욕적 방법(Greedy Method)을 사용한다. 가장 가까운 정점을 찾고, 그 정점을 통해 다른 정점으로의 경로를 갱신한다.	동적 계획법(Dynamic Programing)을 사용한다. 모든 중간 정점을 고려하여 각 쌍의 최단 경로를 계산한다.
시간복잡도	일반적으로 O(V^2), 이 문제의 경우 모든 정점이므로 O(V^3)	O(V^3)
특징	가중치가 음수인 간선이 없는 그래프에 적합하다.	가중치가 음수인 간선이 있어도 적용 가능하나, 음수 사이클은 없어야 한다.

 

각 목적과 특징을 생각해 적절한 알고리즘을 사용하자.