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

www.acmicpc.net/problem/1389

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

import sys
from collections import deque

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().rstrip().split())
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        graph[a].append(b)
        graph[b].append(a)

    def bfs():
        global n
        start = 1
        depth = []
        while start <= n:
            q = deque([start])
            visited = [False] * (n + 1)
            visited[start] = True
            num_depth = [0] * (n + 1)
            while q:
                v = q.popleft()
                for i in graph[v]:
                    if not visited[i]:
                        visited[i] = True
                        q.append(i)
                        num_depth[i] = num_depth[v] + 1
            depth.append(sum(num_depth))

            start += 1
        return depth

    depth = bfs()
    min_val = depth[0]
    ans = 0
    for i in range(1, len(depth)):
        if depth[i] < min_val:
            min_val = depth[i]
            ans = i

    print(ans + 1)

 

이 문제 많이 헤매진 않았지만 어려워서 당황스럽고 풀고나서도 왜이렇게 어려웠나 당황스러운 문제다.

확실히 인접리스트 형태의 문제에 약한듯 하다.

1번 노드부터 n번 노드까지 차례로 방문하면서

다른 노드들과의 depth 의 합을 리스트에 저장시켜놓는다.

그 다음 저장된 depth 를 순회하며 가장 작은 요소의 인덱스를 출력해주면 끝.