문제
알고리즘
- bfs 탐색을 통해 문제를 수행한다.
- 반복문을 통해 모든 친구를 기준으로 탐색한다.
- 친구 관계를 확인하고 탐색하지 않은 친구라면 탐색한다.
- 탐색하면서 탐색하기까지 걸린 횟수를 체크한다.
- 케벤 베이컨의 수가 가장 작은 사람을 인덱스를 이용해서 출력한다.
코드
import sys
from collections import deque
# bfs 탐색
def bfs(v):
queue = deque([v])
visited[v] = 1
while queue:
target = queue.popleft()
# 친구 관계를 확인하고 탐색하지 않은 친구라면 탐색한다.
for i in graph[target]:
if not visited[i]:
# 탐색하기 위한 횟수를 체크한다.
visited[i] = visited[target] + 1
queue.append(i)
n, m = map(int, sys.stdin.readline().split())
# 2차원 그래프를 표현
graph = [[] for _ in range(n + 1)]
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
# 케빈 베이컨의 수를 담는 리스트
res = []
# 반복문을 통해 모든 친구를 탐색한다.
for i in range(1, n + 1):
visited = [0] * (n + 1)
bfs(i)
res.append(sum(visited))
# 가장 작은 케빈 베이컨의 수를 가지고 있는 사람의 인덱스 + 1 을 해주어 출력한다.
print(res.index(min(res)) + 1)
github
'CodingTest > Baekjoon' 카테고리의 다른 글
[baekjoon] 백준 1916번(파이썬): 최소비용 구하기 (0) | 2021.09.02 |
---|---|
[baekjoon] 백준 1753번(파이썬): 최단경로 (0) | 2021.09.01 |
[baekjoon] 백준 1068번(파이썬): 트리 (0) | 2021.08.30 |
[baekjoon] 백준 1245번(파이썬): 농장 관리 (0) | 2021.08.29 |
[baekjoon] 백준 2823번(파이썬): 유턴 싫어 (0) | 2021.08.28 |