케빈베이컨의 6단계 법칙

---

title: “1389 - 케빈베이컨의 6단계 법칙”
date: “2019-02-20”

category: “algorithm”

문제요약

1. 인풋으로 친구관계가 들어온다.
2. 친구, 혹은 친구를 통해 모든 사람을 아는데 필요한 단계가 가장 적은 사람을 구하시오 (단 여러명이라면 번호가 가장 작은 사람을 출력)

접근법

이 문제는 페이스북등 SNS에서 친구들을 건너건너 다양한 사람들을 만날 수 있는 환경에서 누가 가장 많은 사람을 알고 있는가를 계산하는 문제이다. 만약 A 와 B가 친구이고 B가 C와 친구면 A는 B를 통해 C라는 사람을 알 수 있게 되는 것이다. 케빈 베이컨은 A가 2단계를 거쳐 C를 알 수 있다고 했다. 이렇게 모든 사람을 알 수 있다고 할 때 필요한 단계가 가장 적은 사람을 출력하는 것이 이 문제이다.

이 문제도 BFS를 통해 쉽게 풀수 있다.

5	5
1	3
1	4
4	5
4	3
3	2

위와 같이 예제 입력이 들어올 경우 총 5명의 사람에 대해 BFS를 수행하므로써 각각의 케빈 베이컨 수를 구하고 그중 가장 작은 값을 갖는 사람을 출력하면 된다. 위와 같이 표 형태로 표현되어 있으면 한눈에 파악하기 힘들기 때문에 그래프 형태로 표현해 보았다.

각각의 사람들이 여러 단계를 거쳐 알수 있는 사람은 다음과 같다.

 1 -> (3, 4)    -> (2, 5)
 2 -> 3         -> (1, 4) -> 5
 3 -> (1, 2, 4) -> 5
 4 -> (1, 3)    -> (2, 5)
 5 -> 4         -> (1, 3) -> 2

1번은 1단계를 통해 2명, 2단계를 통해 2명을 알수 있기 때문에 1 * 2 + 2 * 2 = 6, 케빈베이컨 수는 6이 된다.
2번은 1단계를 통해 1명, 2단계를 통해 2명, 3단계를 통해 1명을 알 수 있기 때문에 1 * 1 + 2 * 2 + 3 * 1 = 8, 케빈베이컨 수는 8이된다.
3번은 1단계를 통해 3명, 2단계를 통해 1명을 알수 있기 때문에 1 * 3 + 2 * 1 = 5, 케빈베이컨 수는 5가 된다.
4번은 1단계를 통해 2명, 2단계를 통해 2명을 알수 있기 때문에 1 * 2 + 2 * 2 = 6, 케빈베이컨 수는 6이 된다.
5번은 1단계를 통해 1명, 2단계를 통해 2명, 3단계를 통해 1명을 알 수 있기 때문에 1 * 1 + 2 * 2 + 3 * 1 = 8, 케빈베이컨 수는 8이된다.

위와 같이 사람 1명마다 BFS를 수행하여 케빈베이컨 수를 구하고 그중 가장 작은 값을 가진 사람을 출력하면 된다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)