[백준/Python]11780: 플로이드 2

문제

https://www.acmicpc.net/problem/11780
백준 문제집 - 0x1C강 - 플로이드 알고리즘

 

알고리즘: 플로이드-워셜, 역추적

---

풀이

 

플로이드 워셜을 통해 최단경로(최소비용)를 구하고, 경로를 출력해야하는 문제다.
🚨주의해야 할 점은 "시작도시와 도착도시가 같은 경우는 없다." 부분인데, 중복경로가 없다는 게 아니라 "시작도시 != 도착도시"라는 뜻이다.
따라서 간선 정보를 입력받을 시 기존 비용과 비교한 뒤 갱신해야한다.

 

사실 이 문제의 주요 포인트는 역추적이다.
플로이드 워셜을 수행 후, a - b의 최단경로는 a - c - d - b 처럼 구성될 가능성이 높다.
그러므로 최단경로 갱신 시, a - b의 경로도 갱신해주어야 한다.

 

a - b의 최단경로를 구하는 과정을 예시로 보자.
만약 k = c일때 a - c - b가 기존 경로보다 값이 작다면 a - b의 경로 리스트는 [a, c, b]가 되어야 한다.
하지만 모든 경로를 리스트로 관리하긴 부담스러우니, 대신 nxt[i][j] 배열을 이용해 "i에서 j로 가는 경로 중, i 다음에 가야 할 도시"만 저장해두는 방식으로 경로를 압축하여 관리한다.

 

기본적인 셋팅은 간선 정보 저장과 함께 진행한다.

동일 경로가 여러번 주어질 수 있으므로, 기존에 저장된 비용이 있다면 비교해봐야 한다.
a - b의 기존 비용보다 새로운 비용 c가 더 작을 경우 graph[a][b] = c로 저장/갱신시켜준다.

(nxt는 지금은 상관 X. 비용이 어떻든 a 다음에 무조건 b를 가야 하므로 b 저장.)

 

본격적인 경로 갱신은 플로이드 워셜과 함께 진행되는데, k를 거쳐가는 경로가 더 효율적이라면 nxt[a][b]에 nxt[a][k]의 값을 저장하는 방식이다.
즉 "a에서 k로 가는 경로 중, a 다음에 가야 할 도시"를 맵핑시켜주는 것이다.

 

예를들어 a - b의 최단경로 구성이 a - c - d - e - b 라면 nxt배열은 다음과 같이 구성된다.

[a]로 초기화 후 역추적 시작

nxt[a][b] = c
현재까지의 경로 = [a, c]

nxt[c][b] = d
현재까지의 경로 = [a, c, d]

nxt[d][b] = e
현재까지의 경로 = [a, c, d, e]

nxt[e][b] = b
현재까지의 경로 = [a, c, d, e, b]

 

전체 코드

# 메모리: 33432KB / 시간: 212KB
from sys import stdin


input = stdin.readline
INF = int(1e9)

def main():
    n = int(input())
    m = int(input())

    graph = [[INF] * (n+1) for _ in range(n+1)]
    nxt = [[-1] * (n+1) for _ in range(n+1)]  # nxt[a][b] = a에서 b로 가기 위해 방문해야할 첫번째 노드

    # 1. 간선 정보 저장
    for i in range(1, n+1):
        graph[i][i] = 0

    for _ in range(m):
        a, b, c = map(int, input().split())
        # 새로운 비용 c가 기존 비용보다 작을때에만 graph, nxt 갱신
        if c < graph[a][b]:
            graph[a][b] = c
            nxt[a][b] = b  # nxt도 기존 비용보다 작을때에만 갱신!


    # 2. 플로이드-워셜 수행
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                cost = graph[i][k] + graph[k][j]
                # k를 거치는 비용이 기존 비용보다 작다면 갱신
                if cost < graph[i][j]:
                    graph[i][j] = cost
                    nxt[i][j] = nxt[i][k]  # i-k의 경로 값을 i-j에 저장


    def get_path(s: int, e: int) -> list:
        """
        경로 역추적 함수
        - [a, [b, [c, [d, [e]]]]] 이런식으로, 가장 바깥괄호부터 안쪽 괄호까지 파고든다고 생각하면 됨.
        - s가 a -> b -> c -> d -> e로 변화하게 되는것!
        - 진행 과정 예시
            - 초기 path = [a]
            - a에서 e로 가기 위해 가장 첫번째로 방문해야 할 노드 = b, path = [a, b]
            - b에서 e로 가기 위해 가장 첫번째로 방문해야 할 노드 = c, path = [a, b, c]
            - c에서 e로 가기 위해 가장 첫번째로 방문해야 할 노드 = d, path = [a, b, c, d]
            - d에서 e로 가기 위해 가장 첫번째로 방문해야 할 노드 = e, path = [a, b, c, d, e]
        """
        path = [s]
        while s != e:
            s = nxt[s][e]
            path.append(s)
        return path


    # 3. 최소비용 출력
    for i in range(1, n+1):
        print(" ".join(map(lambda x: str(x) if x != INF else "0", graph[i][1:])))

    # 4. 경로 추적 후 출력
    for i in range(1, n+1):
        for j in range(1, n+1):
            # 시작점 == 끝점 이거나, i-j로 가는 경로가 없다면 0 출력
            if i == j or graph[i][j] == INF:
                print(0)
            else:
                path = get_path(i, j)
                print(len(path), *path)


main()

 

블로그를 위해 다시 풀어봤는데... 기존 풀이는 입력데이터 저장 시 아래와 같이 진행됐었다.

    for a, b, c in route:
        if c < dp[a-1][b-1]:  # 기존 경로값보다 작으면 업데이트.
            dp[a-1][b-1] = c
        nxt[a-1][b-1] = b-1

(dp = graph)

보면 c가 기존 값보다 클때/작을때 상관 없이 무조건 nxt를 갱신시킨다.

아무 생각 없이 이 부분이 잘못됐다고 생각하고, 다시 풀 때 수정했는데 진짜 바보였다;;;

1 3 4, 1 3 1이 주어진다면 비용과 관계없이 nxt[1][3] = 3 이다.

다른 곳을 거쳐가는게 최단경로라면 플로이드 워셜 수행 중 알아서 갱신될것이고.

뭐 수정해도 결과값에 차이는 없어서 문제될건 없지만... 생각에 오류가 있었던거니...

어쨌든... 뒤늦게나마 이 바보짓을 발견해서 다행.