n | vertex | return |
---|---|---|
6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] | 3 |
bfs를 이용하여 visited에 해당 노드까지의 길이를 저장.
from collections import deque
def bfs(v, graph, visited):
visited[v] = 0
q = deque()
q.append(1)
while q:
n = q.popleft()
for ad in graph[n]:
if visited[ad] == -1:
visited[ad] = visited[n] + 1
q.append(ad)
return visited
def solution(n, edge):
graph = [[]*(n+1) for _ in range(n+1)]
for a, b in edge:
graph[a].append(b)
graph[b].append(a)
visited = [-1]*(n+1)
v = bfs(1, graph, visited)
cnt = 0
for i in range(len(v)):
if v[i] == max(v):
cnt += 1
return cnt