BOJ(백준) 1389[케빈 베이컨의 6단계 법칙]

안녕하세요, 이번 글에서는 백준 1389번 문제인 “케빈 베이컨의 6단계 법칙” 문제를 함께 해결해 보겠습니다. 이 문제는 각 사람 사이의 거리를 계산하여 케빈 베이컨 수가 가장 작은 사람을 찾는 문제입니다. 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/1389

1. 문제 설명

1) 문제 개요

여러 사람들 사이의 친구 관계가 주어질 때, 각 사람의 케빈 베이컨 수를 계산하여 가장 작은 사람을 찾는 문제입니다. 여기서 케빈 베이컨 수란, 한 사람이 다른 모든 사람들과 연결되는 최소 단계를 의미합니다.

 

2) 입력

• 첫 번째 줄: 사람의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5000)

• 다음 M개의 줄: 친구 관계를 나타내는 두 사람의 번호가 주어집니다. 사람의 번호는 1부터 N까지입니다.

 

3) 출력

• 케빈 베이컨 수가 가장 작은 사람의 번호를 출력합니다. 만약 여러 명일 경우 가장 번호가 작은 사람을 출력합니다.

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 사람의 수와 친구 관계를 입력받아 인접 리스트에 저장합니다.

 

2) BFS를 이용한 거리 계산

• 각 사람에 대해 BFS를 수행하여 다른 모든 사람까지의 거리를 계산합니다.

• 각 사람의 케빈 베이컨 수를 구하고, 가장 작은 케빈 베이컨 수를 가진 사람을 찾습니다.

 

3) 점수 계산

• 각 사람의 케빈 베이컨 수를 계산하여 최종적으로 가장 작은 사람을 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# N: 사람의 수, M: 친구 관계의 수
N, M = map(int, input().split())
# 인접 리스트를 이용하여 친구 관계를 저장
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1  # 입력이 1부터 시작하므로 0부터 시작하도록 조정
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

minNum = sys.maxsize    # 최소 케빈 베이컨 수를 초기화
minIdx = -1             # 최소 케빈 베이컨 수를 가진 사람의 인덱스를 초기화

# 각 사람에 대해 BFS를 수행하여 케빈 베이컨 수를 계산
for i in range(N):
    dist = [-1] * N     # 각 사람까지의 거리를 저장하는 리스트, 초기값 -1
    chk = [0] * N       # 방문 여부를 체크하는 리스트
    q = [i]             # BFS를 위한 큐, 시작점은 i
    chk[i] = 1          # 시작점 방문 체크
    dist[i] = 0         # 시작점의 거리는 0
    
    while len(q) > 0:
        s = q.pop(0)            # 큐에서 하나의 정점을 꺼냄
        for j in adj[s]:        # 꺼낸 정점과 인접한 모든 정점에 대해
            if chk[j] == 0:     # 아직 방문하지 않았다면
                chk[j] = 1      # 방문 체크
                q.append(j)     # 큐에 추가
                dist[j] = dist[s] + 1  # 거리 갱신 (현재 정점의 거리 + 1)
    
    dNum = sum(dist)    # 모든 거리의 합 (케빈 베이컨 수)
    if dNum < minNum:   # 현재의 케빈 베이컨 수가 최소값보다 작다면
        minNum = dNum   # 최소값 갱신
        minIdx = i      # 최소값을 가진 사람의 인덱스 갱신

print(minIdx + 1)       # 1부터 시작하는 인덱스로 출력

4. 코드 설명

1) 입력 받기

• 첫 번째 줄에서 사람의 수 N과 친구 관계의 수 M을 입력받습니다.

• M개의 줄에 걸쳐 친구 관계를 입력받아 인접 리스트 adj에 저장합니다.

 

2) BFS를 이용한 거리 계산

• 각 사람을 시작점으로 BFS를 수행하여 다른 모든 사람까지의 거리를 계산합니다.

• dist 리스트: 각 사람까지의 거리를 저장하는 리스트로, 초기값은 -1입니다.

• chk 리스트: 각 정점의 방문 여부를 체크하는 리스트입니다.

• q 리스트: BFS를 위한 큐입니다.

 

3) 케빈 베이컨 수 계산

• BFS를 통해 계산된 거리를 모두 더해 케빈 베이컨 수를 구합니다.

• 최소 케빈 베이컨 수와 그 사람의 인덱스를 갱신합니다.

 

4) 결과 출력

• 최종적으로 최소 케빈 베이컨 수를 가진 사람의 번호를 출력합니다.

5. Github으로 확인

coTest/BOJ/BOJ01_09_02_1389.py at main · pcy4196/coTest