[백준] 11403 python 플로이드 워셜, deque 풀이와 시간복잡도 비교하기

여러가지 조건에서 최단거리를 구하는 알고리즘 문제가 나오기 때문에 관련 공부는 필수인 듯 하다.

기존에는 다익스트라 알고리즘만 활용가능한 수준이었는데 이번에 11403번 문제를 보면서 플로이드 워셜 알고리즘을 처음 사용해 보았다.

 

처음 풀이에서는 플로이드 워셜 알고리즘을 사용하지 않고, deque를 활용하여 문제를 풀었는데 백준 문제 기준으로 deque를 사용한 풀이의 시간이 덜 소요되는것으로 보였다.

두가지 풀이에서 어떤 점이 소요시간의 차이를 일으켰는지 알아보고자 한다.

---

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

47580

29309

21659

61.491%

문제

가중치 없는 방향 그래프 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. deque 활용

deque를 활용한 풀이는 다음과 같다.

import sys
import time

sys.stdin = open("input.txt")
from collections import deque
n = int(input())
city = [list(map(int, input().split())) for _ in range(n)]

# deque 버전
def solution_deque():
    visit = [[0]*n for _ in range(n)]
    dq = deque()
    for from_first, m in enumerate(city):
        for to_city, moving in enumerate(m):
            if moving == 1 and visit[from_first][to_city] == 0:
                visit[from_first][to_city] = 1
                dq.append(to_city)
                while dq:
                    to_city = dq.popleft()
                    for next_to, next_move in enumerate(city[to_city]):
                        if next_move == 1 and visit[from_first][next_to] == 0:
                            visit[from_first][next_to] = 1
                            dq.append(next_to)

    for i in visit:
        print(*i)

여기서 visit은 방문여부를 체크하기도 하지만, 최종 답을 적기 위해 그 초기값을 0으로 하였다.

 

city 이중배역에 문제로 주어진 간선 정보를 담았다.

이후 첫번째 for loop 에서 현재 확인하고자 하는 노드를 "from_fist" 값으로 하고, from_first와 연결된 노드를 "to_city" 라고 하였다.

from_first 에서 to_city 로 가는 간선이 존재한다면 visit정보를 1로 업데이트 하고, 간선 정보를 deque에 담는다.

이후 deque값이 존재할 동안 (while 조건) 이어지는 간선 정보를 확인한다.

to_city 를 기준으로 for loop로 찾는 도시 "next_to" 의 1인 경우 (next_move가 1) 방문여부를 확인하고 from_first에서 next_to가 연결되었음을 체크한다.

또한, to_city 에서 next_to의 연결정보를 다시 deque에 담아 next_to의 도시에서 시작하는 연결정보를 계속해서 탐색한다.

---

from collections import deque
# from_first = 0
# to_city = 1
city = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]
"""
from_first에서 to_city의 연결정보가 1이므로 방문여부 확인 후 체크한다.
그리고 이어서 탐색하기 위해 해당 연결 정보를 deque에 담는다
"""
dq = deque()
if city[from_first][to_city] == 1 and visit[from_first][to_city] == 0:
	visit[from_first][to_city] = 1
    dq.append(to_city)
    # dq에 담긴 정보에서 이어서 탐색 한다. (from_first에서 시작한 연결정보가 끝날때까지)
    while dq:
    	from_city, to_city = dq.popleft()
        for next_to, next_move in enumerate(city[to_city]):
        	if next_move == 1 and visit[first_from][next_to] == 0:
            	visit[first_from][next_to] = 1
                """
                to_city에서 next_to가 연결되어있다면 from_first에서 next_to도 연결된 것이다.
                방문여부를 체크하고, 이어서 연결정보를 탐색하게 한다.
                """
                dq.append(next_to)

한가지 상황을 예로 들어 과정을 풀이하면 위와 같다. 총 시간복잡도는 N^3으로 확인된다. 단, 자기자신의 노드로 가는 경우는 0이기 때문에 해당 경우의 수는 확인하지 않는다.

 

---

2. 플로이드-워셜 활용

플로이드-워셜 알고리즘이란 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

위 알고리즘을 더욱 잘 활용할수 있는 예제는 "가중치가 있는 간선" 이 주어졌을때 인데, 위 문제의 경우 가중치가 없어 오로지 "연결 가능한 노드인지" 를 확인만 하면 된다.

 

플로이드-워셜 알고리즘으로 i 에서 j 노드로 갈때 k 노드를 거쳐서 갈수있는지 확인하여 i 에서 j 노드의 연결을 확인한다. i에서 j 노드의 모든 수를 확인하는 N^2 시간복잡도에서 k 노드 확인 경우를 추가하여 최종적으로 N^3의 시간복잡도를 보이고, 모든 노드를 확인하여 제외되는 경우는 없다.

def solution_floid():
    """
    i에서 j의 경로를 탐색하면서 거쳐가는 k 노드의 값을 확인, k 값으로 연결된 i, j는 연결가능하다
    """
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
    for row in city:
        print(*row)

---

3. 두 풀이의 풀이시간 차이

2) 동일한 노드수에서 간선 비율의 차이에 따른 시간차이

i. 노드의 수가 14개

당연히 알고리즘으로 풀면 더 빠르겠지! 싶었던 생각이 예제로 소요시간을 확인하며 깨졌다.

노드의 수가 14개이면서, 간선의 비율이 약 25%, 약 52% 약 92% 일때 시간을 측정해 보았다.

# 노드의 수 14 / 간선비율 약 25%
# deque 소요시간 : 0.0006220340728759766
# floyd 소요시간 : 0.0008339881896972656

14
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 1 0 1 0 1 0 1 0 1 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 0

# 간선 비율 약 52%
# deque 소요시간 : 0.0006856918334960938
# floyd 소요시간 : 0.0009648799896240234

14
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0

# 간선비율 약 92%
# deque 소요시간 : 0.0006418228149414062
# floyd 소요시간 : 0.0008568763732910156

14
0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0

 

노드수가 14개일 경우 간선의 비율차로는 플로이드-워셜의 소요시간이 항상 더 길게 나온다.

ii) 노드 수가 5개

# 간선비율 약 80%
# deque 소요시간 : 9.012222290039062e-05
# floyd 소요시간 : 8.797645568847656e-05

5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

# 간선비율 약 20%
# deque 소요시간 : 9.918212890625e-05
# floyd 소요시간 : 9.894371032714844e-05

5
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0

 

노드의 수가 5개이거나, 이의 약 3배인 14개이거나 플로이드-워셜 풀이로 풀었을 경우 소요시간이 더 크게 나오는것을 확인 할 수 있다.

극단적으로 노드의 수가 3개일 경우에는 플로이드-워셜의 소요시간이 더 적게 나오긴 하다

# 간선비율 : 약 33%
# deque 소요시간 : 3.910064697265625e-05
# floyd 소요시간 : 2.9087066650390625e-05

3
0 1 0
0 0 1
1 0 0

 

하지만 보통의 문제에서는 n의 범위가 3까지일리가 없으니... 시간복잡도를 생각한다면 플로이드-워셜이 아닌 deque를 사용한 풀이를 선택해도 될것같다.