https://www.acmicpc.net/problem/1389
나의 풀이
from collections import deque
import sys
input = sys.stdin.readline
n_ct, c_ct = map(int, input().rstrip().split())
conn_dict = {}
for _ in range(c_ct):
s, e = map(int, input().rstrip().split())
if s not in conn_dict:
conn_dict[s] = [e]
else:
conn_dict[s].append(e)
if e not in conn_dict:
conn_dict[e] = [s]
else:
conn_dict[e].append(s)
kebin_type = float('inf')
kebin_n = float('inf')
for i in range(1, n_ct+1):
visit = [0] * n_ct
queue = deque()
queue.append((i, 0))
while queue:
now_pt, now_len = queue.popleft()
for next_pt in conn_dict[now_pt]:
if (visit[next_pt-1] == 0) or (visit[next_pt-1] > now_len + 1):
visit[next_pt-1] = now_len + 1
queue.append((next_pt, now_len+1))
visit[i-1] = 0
now_kebin_n = sum(visit)
if now_kebin_n < kebin_n:
kebin_type, kebin_n = i, now_kebin_n
elif now_kebin_n == kebin_n:
kebin_type = min(kebin_type, i)
print(kebin_type)
시간 복잡도
conn_dict = {} : 연결 딕셔너리 생성 ( 선형 시간 복잡도 )
for i in range(1, n_ct+1) : 모든 경우 케빈 베이컨 수 찾기 ( 선형 시간 복잡도 )
while queue : 케빈 베이컨 수 구하기 모든 경로 탐색 ( 선형 시간 복잡도 )
해당 알고리즘은 이차형 시간 복잡도 : O(n**2)
