[BOJ] 케빈 베이컨의 6단계

https://www.acmicpc.net/problem/1389

1. 아이디어💡

1.1. 문제분석

• 모든 사람들은 다른 모든 사람들에 대해 무조건 친구관계가 연결되게 입력이 주어진다.
• 케빈 베이컨 점수는 특정 사람이 다른 모든 사람들과 관계가 이어지기 위해 거쳐가야하는 관계수를 합한 값이다.

1.2. 해결 방법

플로이드 와샬 알고리즘을 사용한다.

1. 각 사람들의 관계 거리에 대한 값을 저장한 테이블을 생성한다.

	1	2	3	4
1	0	INF	INF	INF
2	INF	0	INF	INF
3	INF	INF	0	INF
4	INF	INF	INF	0

2. 입력으로 받은 관계를 모두 1로 바꿔준다.

	1	2	3	4
1	0	1	INF	1
2	1	0	1	INF
3	INF	1	0	1
4	1	INF	1	0

3. 1행부터 차례대로 자기와 연결된 사람들을 큐에 넣고 큐에서 꺼낸 사람의 행을 탐색해서 연결된 사람을 큐가 꺼내진 행의 사람으로 부터의 거리를 계산해서 기존의 저장된 거리값보다 작다면 새롭게 갱신한다.

   • 예시: 1행에서 2, 4와 연결 되어 있으므로 큐에 삽입한다.
   • 큐에서 꺼내면 2가 나오고 2행에서 연결된 3까지의 거리가 1이다. 따라서 1에서 3까지의 거리는 1+1=2가 된다.

   	1	2	3	4
   1	0	1	2	1
   2	1	0	1	INF
   3	INF	1	0	1
   4	1	INF	1	0

4. 위의 과정을 반복한다.

	1	2	3	4
1	0	1	2	1
2	1	0	1	2
3	2	1	0	1
4	1	2	1	0

위의 예시에선 모든 사람의 케빈 베이컨 점수가 3으로 똑같기 때문에 가장 작은 인덱스인 1을 출력한다.

2. 코드

import sys
from collections import deque
input = sys.stdin.readline

INF = 128
N, M = map(int, input().split())
relationship = [[INF] * N for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    relationship[a - 1][b - 1] = 1
    relationship[b - 1][a - 1] = 1
for i in range(N):
    relationship[i][i] = 0
que = deque()
for i in range(N):
    for j in range(N):
        if i != j and relationship[i][j] < INF:
            que.append((j, relationship[i][j]))
    while que:
        pos = que.popleft()
        for j in range(N):
            if relationship[pos[0]][j] + pos[1] < relationship[i][j]:
                relationship[i][j] = relationship[pos[0]][j] + pos[1]
                que.append((j, relationship[i][j]))
total_score = list(map(lambda x: sum(x), relationship))
print(total_score.index(min(total_score)) + 1)