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

www.acmicpc.net/problem/1389

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

---

접근

처음에 DFS로 탐색을 하여 관계의 합을 구하려고 했다. 하지만 스택을 이용해 풀면 관계의 합이 최소가 되지 않는다는 것을 알게되었다. 따라서 근접한 이웃 먼저 탐색을 하는 BFS로 풀어 통과가 되었다.

로직은 똑같은데 스택을 큐로만 바꿔주었다.

 

구현

사람의 수와 관계의 수를 입력받아 트리를 구성하였다.

N, M = map(int, input().split())
tree = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

 

BFS로 탐색을 하여 관계의 합을 반환하도록 하고 result에 반환된 결과를 담아서 최솟값을 갖는 번호를 출력한다.

result = []
for n in range(1, N+1):
    result.append(bfs(n))

 

BFS에서는 큐를 활용하였고 visited에 각 관계들의 숫자를 입력한다.

탐색을 진행할 때마다 자식노드의 번호에 부모노드의 숫자 + 1을 입력하고

마지막에 노드들의 숫자들을 모두 더하여 반환한다.

def bfs(n):
    q = [n]
    visited = [0 for _ in range(N+1)]
    visited[n] = 1

    while q:
        parent = q.pop(0)
        for child in tree[parent]:
            if visited[child] == 0:
                q.append(child)
                visited[child] = visited[parent] + 1
    total = sum(visited)
    return total

---

전체 코드

import sys
input = sys.stdin.readline

def bfs(n):
    q = [n]
    visited = [0 for _ in range(N+1)]
    visited[n] = 1

    while q:
        parent = q.pop(0)
        for child in tree[parent]:
            if visited[child] == 0:
                q.append(child)
                visited[child] = visited[parent] + 1
    total = sum(visited)
    return total

N, M = map(int, input().split())
tree = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

result = []
for n in range(1, N+1):
    result.append(bfs(n))

tmp = min(result)
for idx in range(len(result)):
    if result[idx] == tmp:
        print(idx+1)
        break