[Solved] BOJ: 1389 | 케빈 베이컨의 6단계 법칙

문제

케빈의 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임
한 사람이 나머지 모든 사람들에 대해 베이컨 게임을 진행해서 나오는 단계들의 총합을 베이컨 수라고 한다.
모든 사람들의 베이컨 수를 구해 그 중 최소의 베이컨 수를 갖는 사람을 구하자.

입력과 출력

입력

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

출력

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

---

문제 해결 요약

1. n명의 유저들을 순회하면서
2. 각각의 베이컨수를 구해
3. 그 중 최소의 베이컨수를 갖는 사람을 출력한다

베이컨수를 구하는 과정-

1. BFS로 인접한 사람들 우선적으로 탐색하며
2. 거리를 1씩 더해준다.

코드 설명

import 및 입력받기

-

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

n, m = map(int, input().split())

• n 유저의 수
• m 친구 관계의 수

유저들의 관계 그래프 생성

유저들이 각각 어떻게 관계를 가지고 있는지 dictionary로 그래프를 생성한다

-

users = {}
for i in range(1, n+1):
    users[i] = []
for _ in range(m):
    u1, u2 = map(int, input().split())
    if u2 not in users[u1]:
        users[u1].append(u2)
    if u1 not in users[u2]:
        users[u2].append(u1)

• dictionary로 유저 그래프 생성
• 1부터 n까지의 key값에 대해 리스트 생성
• m개의 관계를 dictionary에 추가

한 사람의 베이컨 수를 계산하는 함수

한 사람의 베이컨 수를 계산하는 함수를 bfs로 구현한다
-

def bacon(graph, root):
    bacon = [0]*(len(graph)+1) # 베이컨수 저장하는 리스트, 인덱스 1부터 셀거라 1더해줌
    visited = [False]*(len(graph)+1) # 방문 여부 표시 리스트
    visited[root] = True # root는 방문처리
    queue = deque([root])

    while queue:
        cur = queue.popleft() # 현재
        for friend in graph[cur]: # 현재 사람의 친구들을 순회하면서
            if visited[friend] is False: # 방문한 적이 없다면
                bacon[friend] = bacon[cur] + 1 # 현재 사람의 베이컨 수 + 1
                visited[friend] = True # 방문 표시
                queue.append(friend) # 큐에 방문해야할 친구 추가

    return sum(bacon)

• 유저 관계 graph와 베이컨 수 계산의 대상이 되는 사람을 root로 입력받는다
• bacon 베이컨 수를 저장하는 리스트 생성, 인덱스를 1부터 셀 것이므로 길이는 그래프 길이에 +1 만큼으로 설정
• visited 방문 여부를 표시하는 리스트를 True False 리스트로 생성
• 일단 root는 방문처리 해준다
• queue를 생성해준다. root를 시작으로 탐색을 시작하기 때문에 큐에 root를 먼저 담아준다.
• queue가 빌 때까지 while 문을 돌면서
• queue에서 맨 앞에 있는 값을 popleft해 cur변수로 받아와준다.
• cur에 인접한 친구들을 순회하면서
• 방문한 적이 없는 친구라면
• cur의 베이컨수에 +1한 값을 친구의 베이컨 값으로 갱신해준다
• 그리고 이 친구는 방문표시해준다
• 그리고 이 친구의 인접한 친구들을 탐색하기 위해 큐에 이 친구를 넣어준다.
• 마지막에 bacon리스트의 합을 리턴해준다

베이컨의 수가 가장 작은 사람 구하기

-

min_people = 0 # 베이컨의 수가 가장 작은 사람
for i in range(1, n+1):
    if i == 1:
        min_bacon = bacon(users, i)
        min_people = i
    if min_bacon > bacon(users, i):
        min_bacon = min(min_bacon, bacon(users, i))
        min_people = i

print(min_people)

• 1부터 n까지 순회하면서 베이컨의 수가 가장 작은 사람을 갱신해준다.

---

전체 코드

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

# 한 사람의 베이컨 수를 계산하는 함수 ->  BFS
def bacon(graph, root):
    bacon = [0]*(len(graph)+1) # 베이컨수 저장하는 리스트, 인덱스 1부터 셀거라 1더해줌
    visited = [False]*(len(graph)+1) # 방문 여부 표시 리스트
    visited[root] = True # root는 방문처리
    queue = deque([root])

    while queue:
        cur = queue.popleft() # 현재
        for friend in graph[cur]: # 현재 사람의 친구들을 순회하면서
            if visited[friend] is False: # 방문한 적이 없다면
                bacon[friend] = bacon[cur] + 1 # 현재 사람의 베이컨 수 + 1
                visited[friend] = True # 방문 표시
                queue.append(friend) # 큐에 방문해야할 친구 추가

    return sum(bacon)

# n: user의 수, m: 친구 관계의 수
n, m = map(int, input().split())

# user 관계 그래프 생성
users = {}
for i in range(1, n+1):
    users[i] = []
for _ in range(m):
    u1, u2 = map(int, input().split())
    if u2 not in users[u1]:
        users[u1].append(u2)
    if u1 not in users[u2]:
        users[u2].append(u1)

# 1부터 n까지 순회하며 베이컨의 수가 가장 작은 사람을 갱신
min_people = 0 # 베이컨의 수가 가장 작은 사람
for i in range(1, n+1):
    if i == 1:
        min_bacon = bacon(users, i)
        min_people = i
    if min_bacon > bacon(users, i):
        min_bacon = min(min_bacon, bacon(users, i))
        min_people = i

print(min_people)