풀이
'Six Degrees of Separations' theory로도 불리는 이론이다.
자신과는 아무 연관성(inf or V) 없는 사람일지라도, 만약 친구가 한 명 이상 있다면(connected),
대부분 6단계(5명의 관계)를 걸쳐 알 수 있게 된다는 이론이다.
즉, 당신이 6단계를 넘어선다면 아싸일 확률이 매우 높...
문제에서
"모든 사람은 친구 관계로 연결되어져 있다."
라고 하여 주어지는 TC에 대한 별도의 예외처리는 없다.
Floyd Warshall을 이용해 모든 친구 관계에 대해서 최단 단계를 구해주고,
각각의 유저가 모든 유저간에 대한 단계의 합으로이루어진 집합(step) 속 최솟값의 순번을 구하자.
소스코드
출처
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 27110] 특식 배부 [Python] (0) | 2023.04.12 |
|---|---|
| [백준 27182] Rain Diary [Python] (0) | 2023.04.09 |
| [백준 27213] Граничные клетки [Python] (0) | 2023.04.07 |
| [백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 [C] (0) | 2023.04.06 |
| [백준 27239] Шахматная доска [Python] (0) | 2023.04.05 |