L3 : 가장 먼 노드 Python

L3 : 가장 먼 노드 Python

https://school.programmers.co.kr/learn/courses/30/lessons/49189

from collections import defaultdict, deque

def solution(n, edge):
    graph = defaultdict(list)
    for start, end in edge:
        graph[start].append(end)
        graph[end].append(start)
    
    visited = [0]*(n+1) # 각 노드(인덱스)에 1에서부터의 거리를 기록
    visited[1] = 1 # 1부터 시작하기 때문
    dq = deque()
    dq.append(1)
    
    while dq:
        start = dq.popleft()
        for end in graph[start]:
            if visited[end]==0:
                visited[end] = visited[start] + 1
                dq.append(end)
    
    return visited.count(max(visited))

BFS에서 visited는 방문 여부만 기록했는데, 여기서는 각 노드를 지나칠 때마다 거리를 기록하는 용도로 활용해야한다.

#그래프 #BFS