Post

[BOJ]11404. 플로이드

Posted Updated
By your_full_name 9 min read

11404. 플로이드


❌code1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import sys
import heapq


N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
costs = [[0] * (N + 1) for _ in range(N + 1)]
checked = [[False] * (N + 1) for _ in range(N + 1)]  # 비용이 확정된 경로 표시

hq = []  # heapq

for _ in range(M):
    s_city, e_city, cost = map(int, sys.stdin.readline().split())
    costs[s_city][e_city] = cost  # 비용 기록
    heapq.heappush(hq, (cost, s_city, e_city))  # 비용을 기준으로 힙에 추가

while hq:
    # 비용이 가장 적은 경로 추출
    cost, s_city, e_city = heapq.heappop(hq)

    if checked[s_city][e_city]:  # 이미 확정된 도시는 무시
        continue
    checked[s_city][e_city] = True  # 확정 표시
    costs[s_city][e_city] = cost  # 가격 표시

    for city in range(1, N + 1):  # e_city에서 갈 수 있는 다음 도시
        if city == s_city or city == e_city:
            continue  # 출발지나 도착지(city)와 경유지(e_city)가 같으면 무시

        if costs[e_city][city]:  # city로 갈 수 있는 경로가 있는 경우
            heapq.heappush(hq, (cost + costs[e_city][city], s_city, city))

for row in range(1, N + 1):
    print(' '.join(map(str, costs[row][1:])))

시도

  1. 각 경로의 비용을 저장하는 리스트 costs와 최소 비용으로 탐색이 완료된 경로를 표시할 checked 리스트를 사용한다.
  2. 모든 경로는 비용을 기준으로 힙에 저장한다.
  3. 힙을 이용해 비용이 최소인 경로를 추출하여 최소 비용의 경로를 확정하고(checked와 costs 리스트 갱신) 해당 경로에 추가로 더 이동할 수 있는 경로를 찾는다.
    1. 이때 출발지와 도착지, 경유지는 모두 달라야 한다.
    2. 또한 다음 목적지로 갈 수 있는 경로가 존재해야 한다.
  4. 다음 목적지와 그 비용을 출발지와 함께 힙에 추가한다.

문제

힙을 이용해 무조건 최소 비용이 계산될 것이기 때문에 초기 경로의 비용을 costs에 저장할 때 항상 최솟값으로 넣는 과정을 무시해 틀린 답이 나왔다.

경로의 비용이 확정될 때에는(costs[s_city][e_city] = cost) 힙을 사용하기 때문에 항상 그 비용이 최솟값이 된다.

하지만 다른 도시를 경유해 새로운 비용을 계산할 때에는(cost + costs[e_city][city]) 초기에 주어지는 경로의 비용을 함께 사용하며, 이 비용에는 아직 최솟값으로 확정되지 않은 비용이 존재할 수 있어 오류가 발생한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

반례

3
4
1 2 3
3 1 2
1 3 4
1 2 4

wrong
0 3 4
0 0 0
2 6 0

answer
0 3 4
0 0 0
2 5 0


⭕code2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import sys
import heapq


N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
costs = [[0] * (N + 1) for _ in range(N + 1)]
checked = [[False] * (N + 1) for _ in range(N + 1)]  # 비용이 확정된 경로 표시

hq = []  # heapq

for _ in range(M):
    s_city, e_city, cost = map(int, sys.stdin.readline().split())

    # 만약 이미 비용이 적혀있다면 최솟값으로 갱신
    if costs[s_city][e_city]:
        costs[s_city][e_city] = min(cost, costs[s_city][e_city])
    else:
        costs[s_city][e_city] = cost
    heapq.heappush(hq, (cost, s_city, e_city))  # 비용을 기준으로 힙에 추가

while hq:
    # 비용이 가장 적은 경로 추출
    cost, s_city, e_city = heapq.heappop(hq)

    if checked[s_city][e_city]:  # 이미 확정된 도시는 무시
        continue
    checked[s_city][e_city] = True  # 확정 표시
    costs[s_city][e_city] = cost  # 가격 표시

    for city in range(1, N + 1):  # e_city에서 갈 수 있는 다음 도시
        if city == s_city or city == e_city:
            continue  # 출발지나 도착지(city)와 경유지(e_city)가 같으면 무시

        if costs[e_city][city]:  # city로 갈 수 있는 경로가 있는 경우
            heapq.heappush(hq, (cost + costs[e_city][city], s_city, city))

for row in range(1, N + 1):
    print(' '.join(map(str, costs[row][1:])))

시도

초기 경로의 비용을 costs에 저장할 때 항상 최솟값으로 기록하도록 수정했다.

문제와 개선

통과는 되었지만 시간과 메모리 소비가 너무 컸다. 갈 수 있는 경로면 무조건 힙에 추가하는 것이 원인이라 생각해 이 과정에 다음과 같은 조건을 추가했다.

1
2
3
4
5
6
7

        if costs[e_city][city]:  # city로 갈 수 있는 경로가 있는 경우
            # 새로 만들어진 경로의 비용이 아직 기록되지 않은 경우 힙에 추가
            if costs[s_city][city] == 0:
                heapq.heappush(hq, (cost + costs[e_city][city], s_city, city))
            # 현재 경로의 비용보다 이미 기록된 비용이 저렴할 경우에도 힙에 추가
            elif cost + costs[e_city][city] <= costs[s_city][city]:
                heapq.heappush(hq, (cost + costs[e_city][city], s_city, city))

채점 결과를 기준으로 보았을 때 수정 전 코드는 124620 KB의 메모리와 4264 ms의 시간이 쓰였지만 수정 후 코드는 67152 KB의 메모리와 2000 ms의 시간이 쓰여 전체적으로 절반을 절약할 수 있었다.


⭕code3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import sys


N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
costs = [[0] * (N + 1) for _ in range(N + 1)]


for _ in range(M):
    s_city, e_city, cost = map(int, sys.stdin.readline().split())

    # 만약 이미 비용이 적혀있다면 최솟값으로 갱신
    if costs[s_city][e_city]:
        costs[s_city][e_city] = min(cost, costs[s_city][e_city])
    else:
        costs[s_city][e_city] = cost

for via in range(1, N + 1):  # 경유 도시
    for start in range(1, N + 1):  # 출발 도시
        for end in range(1, N + 1):  # 도착 도시
            if start == end:  # 출발지와 도착지가 같다면 무시
                continue

            # 경유지를 거쳐 갈 수 있는 경우
            if costs[start][via] and costs[via][end]:
                if costs[start][end] == 0:  # 한번도 가보지 않은 경로인 경우
                    costs[start][end] = costs[start][via] + costs[via][end]

                else:  # 이미 가봤던 경로라면 경유 도시의 유무에 따라 최솟값으로 갱신
                    costs[start][end] = min(costs[start][end], \
                                            costs[start][via] + costs[via][end])


for row in range(1, N + 1):
    print(' '.join(map(str, costs[row][1:])))

시도

이 문제가 전형적인 플로이드–와샬 알고리즘 문제인 걸 뒤늦게 알고 이를 적용했다. 알고리즘 구현은 이 글과 이 글을 참고하였다.

채점 결과를 기준으로 보았을 때 이 코드는 29452 KB의 메모리와 1128 ms의 시간이 쓰여 수정한 code2보다 전체적으로 절반이 절약되었다.


요약

모든 정점에서 모든 정점으로 가는 경로의 최소 비용은 힙을 이용해 구할 수 있다. 하지만 플로이드–와샬 알고리즘을 사용하는 것이 더 효율적이다.

Algorithm_problem_solving
BOJ
This post is licensed under CC BY 4.0 by the author.