1389 케빈 베이컨의 6단계 법칙 / DFS, BFS

 

선택해야하는 알고리즘

최단거리 = BFS

• BFS는 가까운 노드부터 탐색하기 때문에 첫 방문 = 최단거리임이 보장됨
• 미로 탈출 (1칸 이동이 비용 1일 때)
• 각 노드까지 몇 단계만에 갈 수 있는지
• 최단 이동 횟수, 최단 거리 찾기

모든 경로를 다 탐색하고 싶을 때 = DFS

• 모든 경로를 다 탐색하고 싶을 때
• 모든 경우의 수를 보고 싶을 때 (조합, 순열, 경로)
• 백트래킹 (N-Queen, 스도쿠, 조합 등)
• 사이클 찾기

=> 그러므로 해당 문제에서는 반드시 BFS를 사용해야 함

 

 

기준 노드에서부터 다른 노드까지의 거리

1. distance = [0] * (n + 1) 의미

• 모든 거리를 처음엔 0으로 초기화

 

n = 5
distance = [0] * (n + 1)
print(distance)
# 출력: [0, 0, 0, 0, 0, 0]
# 인덱스:  0  1  2  3  4  5

---

 2. distance[i] = distance[current] + 1 

• current는 지금 방문 중인 노드
• i는 current와 연결된 이웃 노드
• 시작 노드가 1
• current = 1 일 때, i = 2 라면
  • 1번에서 2번까지 가는 거리 = distance[1] + 1 = 0 + 1 = 1

distance[i] = distance[current] + 1

 

-> 이렇게 하면, BFS 특성상 최단 거리가 자동으로 계산됨

 

정답

from collections import deque

def BFS(graph, start, n):
    queue = deque()
    queue.append(start)
    visited = [False] * (n + 1)
    distance = [0] * (n + 1) # [0, 0, 0, 0, 0, ...], 해당 노드 기준으로 나머지 노드까지의 최단 거리, distance = [0, 0, 1, 2, 1]
    visited[start] = True # "1번 노드 기준으로 각 노드까지의 최단거리"

    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if visited[neighbor] is False:
                queue.append(neighbor)
                distance[neighbor] = distance[current] + 1
                visited[neighbor] = True

    return sum(distance[1:])

n, m = map(int, input().split()) # 정점의 수, 간선의 수
con = []
for _ in range(m):
    a, b = map(int, input().split())
    con.append((a, b))

graph = []
for _ in range(n + 1):
    graph.append([])

for a, b in con:
    graph[a].append(b)
    graph[b].append(a)

ans = []
min_score = 100 # 가장 무한대로 큰 수
for i in range(1, n + 1):
    score = BFS(graph, i, n)
    if score < min_score:
        min_score = score
        ans = [i]
    elif score == min_score:
        ans.append(i)

ans.sort()
print(ans[0])