728x90
풀이 1: 플로이드-워셜
플로이드-워셜: 모든 정점 쌍 최단 거리 계산
시간 복잡도는 O(N^3) - 이 문제는 N 최댓값 100이므로 이 문제에서 사용할 수 있다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
# 거리 배열 초기화
INF = sys.maxsize
dist = [[INF] * (N+1) for _ in range(N+1)]
# 자신과의 거리는 0으로
for i in range(1, N+1):
dist[i][i] = 0
# 친구 관계 입력
for _ in range(M):
A, B = map(int, input().split())
dist[A][B] = 1
dist[B][A] = 1
# 플로이드-워셜
for k in range(1, N+1):
for i in range(1, N+1):
for j in range(1, N+1):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
min_bacon_num = INF
result_person = -1
for i in range(1, N+1):
bacon_num = sum(dist[i][1:])
if bacon_num < min_bacon_num:
min_bacon_num = bacon_num
result_person = i
print(result_person)
풀이2: BFS
플로이드-워셜보다 시간복잡도 측면에서 더 유리하다.
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
# 그래프 - 인접리스트
graph = [[] for _ in range(N + 1)]
# 친구 관계 입력
for _ in range(M):
A, B = map(int, input().split())
graph[A].append(B)
graph[B].append(A)
# BFS 함수 정의
def bfs(start):
distances = [-1] * (N + 1)
queue = deque([start])
distances[start] = 0
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if distances[neighbor] == -1:
distances[neighbor] = distances[current] + 1
queue.append(neighbor)
return distances
# 모든 사용자에 대해 케빈 베이컨 수 계산
min_bacon_num = sys.maxsize
result_person = -1
for i in range(1, N + 1):
distances = bfs(i)
bacon_num = sum(distances[1:]) # 1번 사용자부터 N번 사용자까지의 거리 합
if bacon_num < min_bacon_num:
min_bacon_num = bacon_num
result_person = i
print(result_person)
플로이드-워셜 알고리즘과 BFS 비교
플로이드-워셜 알고리즘과 BFS는 그래프에서 최단 경로를 찾기 위해 사용되지만, 각각의 알고리즘은 다른 상황에 적합하다.
플로이드-워셜 알고리즘
- 특징: 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘이다.
- 시간 복잡도: (O(N^3))
- 사용 경우: 그래프가 밀집되어 있고, 모든 노드 쌍 간의 최단 경로를 필요로 할 때 적합하다. 이는 그래프의 모든 노드 쌍에 대해 최단 경로 정보를 한꺼번에 구해야 할 때 유용하다.
- 제한 사항: 큰 그래프에서는 (O(N^3)) 시간 복잡도가 비효율적일 수 있다.
BFS (Breadth-First Search)
- 특징: 단일 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. BFS는 주로 가중치가 동일한 (예: 가중치가 1인) 그래프에서 사용된다.
- 시간 복잡도: (O(N + M)) (여기서 (N)은 노드의 수, (M)은 엣지의 수)
- 사용 경우: 단일 소스에서 다른 모든 노드까지의 최단 경로를 필요로 할 때 적합하다. 특히 무방향 그래프나 모든 엣지 가중치가 동일한 그래프에서 사용된다.
- 제한 사항: 단일 소스에서 출발하는 경우에만 최단 경로를 찾을 수 있다. 모든 노드 쌍에 대해 최단 경로를 찾으려면 각 노드에서 BFS를 실행해야 한다.
비교와 선택 기준
- 플로이드-워셜 사용 시기:
- 모든 노드 쌍에 대한 최단 경로가 필요할 때
- 그래프가 비교적 작은 경우 (노드 수가 적을 때)
- 가중치가 음수일 때 (하지만 음수 사이클이 없는 경우)
- BFS 사용 시기:
- 단일 출발점에서 다른 모든 노드까지의 최단 경로가 필요할 때
- 그래프의 엣지가 가중치가 동일할 때
- 그래프가 큰 경우 (노드 수가 많을 때)
결론
플로이드-워셜은 특정 조건에서 매우 유용하지만, 큰 그래프에서는 비효율적일 수 있다. BFS는 단일 출발점에서 최단 경로를 찾는 데 적합하며, 그래프의 크기와 관계없이 효율적이다. 따라서, 그래프의 특성과 문제의 요구 사항에 따라 적절한 알고리즘을 선택해야 한다. 모든 상황에서 BFS로 플로이드-워셜을 대체할 수는 없지만, 특정 조건에서는 BFS가 더 효율적일 수 있다.
728x90
