문제 (백준-1389 케빈 베이컨의 6단계 법칙)
문제 링크 : https://www.acmicpc.net/problem/1389
문제 이해
내용 요약:
-
케빈 베이컨의 6단계 법칙: 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람들로 연결될 수 있다는 법칙이다.
-
케빈 베이컨의 6단계 법칙에 의해 모든 사람은 다른 사람들이 자신의 지인의 몇번째 사람인지 알 수 있다.
-
입력에 주어지는 사람의 수와 친구관계를 통해 각 사람마다의 친구 단계의 합을 구하고 그 중에서 가장 작은 사람을 출력하는 내용이다.
구할 것:
모든 사람들은 자신을 제외한 모든 사람들과의 단계의 합을 구합니다. 그 후 그 단계의 합이 가장 작은 사람을 출력하면됩니다. 만약 합이 같은 사람이 있다면 사람의 번호가 가장 작은 사람을 출력합니다.
문제 접근
이 문제는 입력의 내용만 보더라도 그래프 탐색인 것이 눈에 보였습니다!
DFS, BFS중 무엇을 쓸까 고민해보았습니다. 저는 친구관계를 그림을 그려보았고 결과적으로 BFS를 써야겠다 생각했습니다.
위 그래프는 문제에서 주어진 테스트케이스의 그래프를 그려보았습니다.
빨간 숫자는 1번 노드에서 각 노드에 도달하는데 까지의 단계를 표시한 것입니다.
BFS를 통해 풀면 정말 간단하게 풀릴 것 같아 보입니다!
코드
import sys
input = sys.stdin.readline
from collections import deque
# n : 유저의 수, m: 친구 관계의 수
n, m = map(int, input().strip().split())
graph = [[] for _ in range(n + 1)]
# 무방향 그래프
for _ in range(m):
idx, fri = map(int, input().strip().split())
graph[idx].append(fri)
graph[fri].append(idx)
min_result = int(1e9)
# 딕셔너리 이용
# 탐색 후 방문하지 않은 노드라면 value에 횟수를 저장한다.
def bfs(start):
visited = [False] * (n + 1)
result = [0] * (n + 1)
sum = 0
result[start] = 0
visited[start] = True
queue = deque()
queue.append(start)
while queue:
now = queue.popleft()
for i in graph[now]:
if visited[i] == False:
result[i] = result[now] + 1
sum += result[i]
visited[i] = True
queue.append(i)
return sum
for i in range(1, n + 1):
total = bfs(i)
if min_result > total:
index = i
min_result = total
print(index)저는 구현할 때 인접 노드를 저장할 graph, 방문여부를 확인하는 visited, 각 사람마다 단계를 저장하기 위한 result배열을 이용하였습니다.
후기
문제는 길었지만 이해하고나니 정말 쉽게 푼 문제였습니다. 이 방법 말고도 플로이드 워셜로 풀기가 가능합니다! 같은 문제이지만 그 문제를 해결하기 위한 방법이 여러가지인 것을 보니 답을 구하는데 있어 정말로 정답은 없는 것 같습니다! 항상 편협한 사고에서 깨어있어야 한다는 것을 느꼈습니다!
