[BOJ] 1389: 케빈 베이컨의 6단계 법칙 [그래프 탐색](Python)

문제 링크

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

1389번: 케빈 베이컨의 6단계 법칙

 

소스 코드

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

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

# 무방향 그래프 입력받기
graph = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

answer = [] # 최종 결과 리스트 초기화

def bfs(start):
    cnt = 0 # 이동 횟수를 카운트

    visited = [False] * (n+1) # 방문 여부 초기화
    visited[start] = True
    q = deque([])
    q.append((0,start)) # 이동 횟수, 출발점

    while q:
        # 이동 횟수, 현재 노드
        step,cur = q.popleft()
        
        for next in graph[cur]:
            if not visited[next]: # 방문한 적이 없는 경우
                visited[next] = True # 방문 처리
                q.append((step+1,next)) # 큐에 추가
                cnt += (step + 1) # step 누적

    # (누적된 카운트,시작 노드)를 최종 결과에 추가
    answer.append((cnt,start))

# 모든 노드를 출발점으로 삼아 확인
for i in range(1,n+1):
    bfs(i)

# 카운트 기준 오름차순 정렬
answer.sort()

# 카운트가 가장 작은 것의 시작 노드를 출력
print(answer[0][1])

 

해설

• BFS를 이용해 누적된 이동 횟수를 결과 리스트에 추가
• 무방향 그래프

BFS를 통해 그래프를 탐색하고 이동할 때마다 이동 횟수를 누적한 뒤 결과 리스트에 추가하는 방식으로 풀이했다.

 

 

무방향 그래프

우선 입력에 따라 무방향 그래프를 생성하면 된다.

무방향 그래프란 a에서 b가 연결되어 있으면 b에서 a로도 갈 수 있다는 뜻이다. 즉 양쪽 다 이동할 수 있게끔 둘 다 추가해줘야 한다는 것이다.

 

 

BFS 처리 과정

1부터 n까지의 노드에 대해 전부 BFS를 실행한다. BFS는 시작 노드를 매개변수로 받는다. 이 시작 노드에서 연결된 모든 노드들을 다 확인하고 함수가 종료된다. 함수가 종료되기 직전에 누적된 이동 횟수를 최종 결과 리스트에 추가해둔다.

 

BFS 과정은 다음과 같다.

 

1) 방문 여부를 확인할 방문 리스트를 생성한다.

 

2) 시작 노드로 큐를 만들고, 시작 노드는 방문 처리해준다.

 

3) 시작 노드에서 이동할 수 있는 다음 노드들을 graph를 통해 확인한다.

visited에서 방문 여부를 확인하고 방문한 적이 있으면 다음 노드를 확인하고, 방문한 적이 없으면 방문 처리 후 큐에 추가한다.

큐에 추가할 때는 현재 이동한 것보다 한 번 더 이동해야 하므로 'step + 1'을 해준다.

큐에 추가함과 동시에 step + 1만큼 cnt에 누적한다.

 

4) 모든 노드에 대한 방문이 끝났으면 쌓인 cnt와 출발 노드를 튜플로 묶어 최종 결과 리스트에 추가한다.

 

위 과정이 끝나면 최종 결과 리스트에는 (cnt,출발 노드)로 가득 차 있을 것인데, 

우리는 cnt가 가장 작은 값을 뽑아내야 하므로 sort를 통해 오름차순 정렬한다.

 

그리고 맨 앞의 값 중 출발 노드를 꺼낼 수 있도록 인덱스 [1]로 접근하면 된다.