[BOJ/python] 11403: 경로 찾기 (+ 플로이드-워셜 알고리즘)

문제

✔️ silver 1
그래프 이론
그래프 탐색
최단 경로
플로이드–워셜

문제 흐름

처음에는 그래프에서 그나마 안다고 할만한 게 BFS, DFS 뿐이라서 바로 그쪽으로 접근했다.
방문 가능 여부만 체크하는 것이고 가중치도 없는 그래프이기 때문에 괜찮을 것이라고 생각했다.
근데 생각할수록 비효율적이고 어딘가 생각처럼 수행이 안되고,
무엇보다 손으로 이론적으로 풀었을 때 흐름이 보여야하는데 흐름이 잘 보이지 않았다.
그래서 무슨 알고리즘인지 확인 후 풀게 되었다.

플로이드-워셜 알고리즘은 처음 들어보는 알고리즘이었다.
그래서 문제 풀이를 찾아보는게 아니라 플로이드-워셜 알고리즘에 대해서 찾아봤다.

간단히 요약하자면 위와 같다.
진행 순서를 글으로만 보면 이해가 잘 안 될 수 있다.
플로이드 워셜 알고리즘의 목적은 최단 경로를 구하는 것이기 때문에
현재 $D_{ab}$의 길이와 $k$를 거쳐서 오는 경우인 $D_{ak}+D_{kb}$중 더 작은 값을 취하도록 반복하는 것이다.
$N$개의 노드에 대해 $N \times N$개의 조합을 계산하므로 시간복잡도는 $O(N^{3})$이다.

새롭게 학습한 알고리즘이기 때문에 문제가 해결되는 과정을 직접 손으로 확인해봤다.
원래의 FW 알고리즘 점화식에서 문제에 맞게 점화식을 변형했다.
$D_{ab}$가 존재하거나 $k$를 거쳐서 오는 경우인 $D_{ak}$ AND $D_{kb}$가 존재하면 경로가 존재한다고 말할 수 있겠다! 라고 생각했다.
그래서 점화식은 이렇게 잡았다.

AND와 OR를 오랜만에 수식 기호로 보니 굉장히 낯설다....

코드

# 경로 찾기
# graph

import sys
input = sys.stdin.readline

def fw(g):
    l = len(g)
    for i in range(l):
        # print(i)
        for x in range(l):
            for y in range(l):
                g[x][y] = (g[x][y]) or (g[x][i] and g[i][y])
        # print(g)


if __name__ == "__main__":
    n = int(input())
    g = [list(map(int, input().split())) for i in range(n)]

    fw(g)
    for res in g:
        print(*res)

마무리

오랜만에 완전히 새로운 알고리즘을 공부해서 즐거웠다.
손으로 직접 풀어내려가는 것도 재밌었다.
근데 pprint를 통해 출력을 하며 확인하고 싶었는데 왜인지 pprint가 먹히지 않았다.
저번에도 그랬던거 같은데 왜인지 알아봐야겠다.
플로이드-워셜 알고리즘 참고 블로그