코딩테스트 고득점 Kit - 그래프 1 (Level 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import defaultdict
from queue import deque


# w - f - i
def bfs(graph, src):
    ds = {src: 0}
    q  = deque([src])

    while q:
        cur_v = q.popleft()
        for next_v in graph[cur_v]:
            if next_v not in ds:
                ds[next_v] = ds[cur_v] + 1
                q.append(next_v)
    return ds

def solution(n, vertex):
    graph = defaultdict(set)
    for v1, v2 in vertex:
        graph[v1].add(v2)
        graph[v2].add(v1)

    ds = bfs(graph, 1)
    max_val = max(ds.values())
    return len([v for v, d in ds.items() if d == max_val])