[오답노트] 백준 #11403 경로 찾기 (파이썬) : 플로이드-워셜

오늘의 한 마디
그래프 이론은 엄청 어려운 줄 알았는데, 이 문제만 놓고 보면 굉장히 심플하다!
코드를 보니까 공부할 의욕이 생긴다.

• Baekjoon 문제 링크
• solved.ac > 문제 > CLASS 3에 수록된 문제입니다.

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력 1

3
0 1 0
0 0 1
1 0 0

예제 출력 1

1 1 1
1 1 1
1 1 1

예제 입력 2

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

예제 출력 2

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

---

발상

Solution #1

딱 봐서 무슨 문제인지 감이 안 올 때는,
그래도 문제 밑에 숨겨 있었던 알고리즘 분류 정도는 보고 시작하는 편이다.

이 문제의 알고리즘 분류는 그래프 이론, 플로이드–와샬 이다.

하지만 나는 그래프 이론 뭐 다익스트라, 벨만-포드는 그때는 배웠어도 지금 생각하면 하나도 기억 나지 않는 수준이기 때문에 그래프 이론을 코드로 짤 자신이 없었다.

나동빈님의 플로이드 와샬(Floyd Warshall) 알고리즘을 찾아서 대충 읽어보았는데,
무슨 소리인지 대충 봐서는 이해가 잘 되지 않았다.

그래서 내가 알고 있는 dfs/bfs 탐색 기법을 이용해서 꾸역꾸역 짜보았다.

import sys

N = int(sys.stdin.readline().rstrip())

graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

# 플로이드 와샬(Floyd Warshall) 알고리즘
# https://blog.naver.com/ndb796/221234427842

# 다익스트라 : 하나의 정점에서 출발해서 다른 모든 정점으로의 최단 거리
# 플로이드 와샬 : 모든 정점에서 출발해서 다른 모든 정점으로의 최단 거리 -> 기본적으로 다이나믹 프로그래밍

# 그런데 이 문제에서는 거리 값을 구하는 게 아니라 그냥 연결되어있는지만 알면 되는데? 

rv = []
for i in range(N):
    rv.append(graph[i][:])

def mark_circular(path, i):
    # [1, 2, 3, 4, 5, 3] 라면, (3,5)는 1이다. 
    # [1, 2, 3, 4, 5, 3, 4, 5]까지 늘리고 mark_terminated 하면 안 됨?
    start = path.index(i)
    circular_part = path[start:]
    path.extend(circular_part)
    mark_terminated(path)


def mark_terminated(path):
    for i in range(len(path)):
        for j in range(i+1, len(path)):
            rv[path[i]][path[j]] = 1
        
def dfs(path):
    latest = path[-1]
    is_circular = False
    for i in range(N):
        if graph[latest][i]:
            if i in path:
                mark_circular(path, i)
                return            
            path.append(i)
            dfs(path)
    if not is_circular:
        mark_terminated(path)
            
    
for i in range(N):
    for j in range(N):
        if graph[i][j]:
            dfs([i, j])
for line in rv:
    print(' '.join(map(str, line)))

코드를 직접 읽어볼 사람은 몇 없겠지만, 발상을 간단히 설명하자면 이러하다.

예전에 풀었던 탐색 문제 중에 이동 경로를 누적해가면서 풀었어야 하는 문제가 있었는데, 그때 생각이 나서 그런 느낌으로 만들어보았다.

1. dfs를 이용해 내가 이동한 정점 정보를 리스트에 append 해가면서 dfs를 돈다.
2. 그러다가 다음 두 가지 경우에 걸리면 mark한다.
   1. i in path인 경우, 순환 구조이므로 mark_circular 함수로 이동한다. mark_circular 함수에서는 순환되는 부분만 다시 path 뒤에 중복으로 붙여넣어 mark_terminated로 이동한다.
   2. not is_circular인 경우, 여기서 정점 연결 관계가 끝나고 mark_terminated로 이동한다.

mark_terminated에서는 무슨 일을 하는가?

def mark_terminated(path):
    for i in range(len(path)):
        for j in range(i+1, len(path)):
            rv[path[i]][path[j]] = 1

예를 들어, [1, 2, 3, 2, 3]이는 path가 들어왔다고 하자.
그렇다면, [1, 2], [1, 3], [1, 2], [1, 3], [2, 3], [2, 2], [2, 3], [3, 2], [3, 3], [2, 3]이 mark 되는 것이다.

예상 입출력이 나오길래 이게 되네? 라는 생각을 가지고 제출해봤다.

하지만 시간 초과!

Solution #2

아니, 도대체 플로이드 와샬이 뭔데?

아래 풀이를 일단 보고 마저 설명한다.

---

풀이

import sys

N = int(sys.stdin.readline().rstrip())

graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))
    

for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] and graph[k][j]:
                graph[i][j] = 1

for row in graph:
    print(' '.join(map(str, row)))

입력과 출력 부분을 빼고, 순수 플로이드-와샬 알고리즘 부분을 보면 다음과 같다.

for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] and graph[k][j]:
                graph[i][j] = 1

와!

위에서 장황하게 나눴던 조건이, 이 코드 하나면 다 해결되는 게 정말 매력적이지 않은가?

처음 문제를 접했을 때, 뭔가 이런 느낌으로 풀 수도 있지 않을까 생각을 하긴 했었는데...
코드 구현으로 이어지지 못한 까닭은 바로 [1, 2, 3, 1]인 경우면, 하나만 경유하는 게 아니라 2와 3 둘다 경유해야 [1, 1]을 채울 수 있을 거 같은데 그 경우의 수를 못 담을 것 같다라는 생각에서 기원했다.

그런데 위 알고리즘은 그 경우의 수도 담는다.
(i -> k -> j 순으로 설명한다.)

1) 1->2->3에서 1->3 체크 -> 1->3->1에서 1->1 체크.
또는
2) 2->3->1에서 2->1 체크 -> 1->2->1에서 1->1 체크.

가운데 있는 k값이 가장 바깥 루프이므로, 2)번 방법으로는 알고리즘이 흘러가지 않는다. 하지만 1)번 방법으로는 흘러가기 때문에 1->1은 체크된다.

---

그렇다면, [1, 3, 2, 1]이라면 어떨까?

1) 1->3->2에서 1->2 체크 -> 1->2->1에서 1->1 체크.
2) 3->2->1에서 3->1 체크 -> 1->3->1에서 1->1 체크.

이번에는 1)번 방법이 아닌 2)번 방법으로 흘러가면서 1->1이 체크된다.

이게 되는 게 우연일까?

그 원리를 차근차근 생각해보면 그렇지 않다는 걸 알 수 있다.
예를 들면, 조금 더 길게 [1, 3, 5, 2, 1]을 해보자.

과연 제일 먼저 연결되는 부분이 어디일까?
연결 고리가 가장 낮은 숫자, 즉 5->2->1에서 5->1을 체크하는 부분이다.

이제, [1, 3, 5, 2, 1]은 [1, 3, 5, 1]이 되었고, 연결고리는 2 이하일 수 없다.

그다음 연결되는 부분이 어디일까?
1->3->5에서 1->5를 체크하는 부분이다.

이제, [1, 3, 5, 1]은 [1, 5, 1]이 되었고, 연결고리는 3 이하일 수 없다.
그다음 남은 1->5->1은 k=5일 때 체크될 수 있으므로, 1->1도 체크된다.

이것이 k를 가장 밖으로 빼라는 이유다.

---

이걸 이해하고 나서 다시 나동빈님의 플로이드 와샬(Floyd Warshall) 알고리즘을 읽어보았는데, 이해가 아주 잘 되었다.

단순히 경로가 연결되어 있는지를 보는 것을 넘어서,
각 간선별로 가중치가 주어져 있고, 최소 비용을 찾고 싶을 때는
위의 코드를 약간 각색한 아래의 코드를 사용하면 된다.

for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] + graph[k][j] < graph[i][j]:
                graph[i][j] = graph[i][j] + graph[k][j]

물론, 이때는 graph에 0/1이 아니라 가중치 값이 들어있다.