백준 11657번 Floyd-Warshall

서론

11404번: 플로이드

기본적인 그래프를 탐색하는 문제이고 Dijkstra를 사용해서도 풀 수 있는 문제입니다. 하지만 Floyd-Warshall알고리즘으로 푸는 방법이 존재했기 때문에 이걸로 풀어보았고 몰랐던 개념이기 때문에 학습을 하고 풀었더니 맞았습니다. Floyd-Warshall 알고리즘은 Dijkstra보다 시간복잡도가 O(V^3)로 안 좋다는 단점이 있지만, Vertex의 수가 작으면 한 번에 모든 경로를 구할 수 있다는 장점이 있습니다.

제한 조건

• 시간제한 - 1초

시간제한은 1초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. Floyd-Warshall 알고리즘은 O(V^3)의 시간 복잡도를 가지고, 문제의 조건에서 V=5이므로 충분합니다. V가 조금만 커져도 V^3을 감당할 수 없으므로 V가 작은 경우에만 사용할 수 있습니다.

• 메모리 제한 - 256MB

메모리 제한은 256MB입니다. 그래프를 탐색하는 문제를 풀다 보니 기본적으로 그래프 자체를 선언하거나, 일반적으로 사용하는 visited나 dist_list, DP 등을 선언하는 데는 메모리 제한이 크게 문제가 되지 않습니다. 또 Floyd-Warshall 알고리즘은 Dijkstra에서 사용하는 힙같은 다른 자료구조를 사용하지 않고 for 문만을 돌리기 때문에 메모리 제한은 충분합니다.

Floyd-Warshall

모든 정점에서 모든 정점까지의 최단 거리를 구해야 하는 문제이기 때문에 Floyd-Warshall 알고리즘을 사용해야 합니다. 모든 정점에서의 최단 거리를 담고 있는 최단 거리 리스트를 사용합니다. (dist_list[vertex_num][vertex_num]) row는 시작 정점이고 col은 도착 정점입니다. 즉 dist_list[3][4] = 10이면 정점 3에서 시작해서 정점 4로 가는 최단 거리는 10이라는 소리입니다.

이 알고리즘은 mid라는 중간 점을 두고 시작->mid->끝의 모든 경로를 확인하여 최단 경로를 갱신합니다.

import sys
input = sys.stdin.readline

vertex_num, edge_num = int(input()), int(input())


def make_dist(vertex_num, edge_num):
    dist_list = [[sys.maxsize] * (vertex_num) for __ in range(vertex_num)]
    for i in range(vertex_num):
        dist_list[i][i] = 0

    for i in range(edge_num):
        start, end, weight = map(int, input().split())
        if dist_list[start-1][end-1] == sys.maxsize:
            dist_list[start-1][end-1] = weight
        else:
            dist_list[start-1][end-1] = min(weight, dist_list[start-1][end-1])
    return dist_list


def Floyd_Warshall(vertex_num, dist_list):
    for mid in range(vertex_num):
        for row in range(vertex_num):
            for col in range(vertex_num):
                dist_list[row][col] = min(
                    dist_list[row][col], dist_list[row][mid]+dist_list[mid][col])


dist_list = make_dist(vertex_num, edge_num)
Floyd_Warshall(vertex_num, dist_list)


for row in dist_list:
    for dist in row:
        if dist == sys.maxsize:
            print(0, end=' ')
        else:
            print(dist, end=' ')
    print()

생각

*추가

위의 방법은 최단 경로에 따른 weight 값만 갱신하기 때문에 최단 경로 자체는 구하지 못합니다. 최단 경로를 구하려면 최단 경로에서 이전 vertex를 담고 있는 list를 한 개 더 사용하면 됩니다. 아래 코드와 같이 prev_list를 사용할 수 있고, 최단 경로 갱신 시 그 최단 경로로 가기 위한 전의 점을 담으면 됩니다.

from pprint import pprint
import sys
input = sys.stdin.readline

vertex_num, edge_num = int(input()), int(input())


def make_dist(vertex_num, edge_num):
    dist_list = [[sys.maxsize] * (vertex_num) for __ in range(vertex_num)]
    prev_list = [[-1] * (vertex_num) for __ in range(vertex_num)]
    for i in range(vertex_num):
        dist_list[i][i] = 0

    for i in range(edge_num):
        start, end, weight = map(int, input().split())
        if weight < dist_list[start-1][end-1]:
            dist_list[start-1][end-1] = weight
            prev_list[start-1][end-1] = start
    return dist_list, prev_list


def Floyd_Warshall(vertex_num, dist_list):
    for mid in range(vertex_num):
        for row in range(vertex_num):
            for col in range(vertex_num):
                if dist_list[row][col] > dist_list[row][mid]+dist_list[mid][col]:
                    dist_list[row][col] = dist_list[row][mid] + \
                        dist_list[mid][col]
                    prev_list[row][col] = prev_list[mid][col]


dist_list, prev_list = make_dist(vertex_num, edge_num)
Floyd_Warshall(vertex_num, dist_list)
pprint(prev_list)


for row in dist_list:
    for dist in row:
        if dist == sys.maxsize:
            print(0, end=' ')
        else:
            print(dist, end=' ')
    print()

# prev_list에서 최단경로 뽑는 과정
path_list = [[-1]*vertex_num for __ in range(vertex_num)]
for row in range(vertex_num):
    for col in range(vertex_num):
        path_list[row][col] = []
        path_list[row][col].append(col+1)
        start = row
        end = col
        while start != end:
            path_list[row][col].append(prev_list[start][end])
            end = prev_list[start][end] - 1

for i in range(vertex_num):
    for j in range(vertex_num):
        print(f'{i+1}=>{j+1}경로: {list(reversed(path_list[i][j]))}')