가장 먼 노드

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

def init_graph(edges):
    graph = dict()
    for edge in edges:
        [node1, node2] = edge
        if node1 not in graph.keys():
            graph[node1] = set()
        if node2 not in graph.keys():
            graph[node2] = set()
        graph[node1].add(node2)
        graph[node2].add(node1)
    return graph

2만개의 노드 중 5만개 이하의 간선이 있는 그래프는 인접행렬보다는 희소 행렬의 형태로 구현하는 것이 효율적이다. 보통 연결 리스트 또는 일반 리스트를 사용하지만, 본 문제에서는 로직의 구현 편의성을 위해 Python set() 자료구조를 사용했다.

def solution(n, edges):
    graph = init_graph(edges)
    
    visited_nodes = set()
    current_nodes = set()
    next_nodes = set([1])
    
    while next_nodes:
        current_nodes = next_nodes
        next_nodes = set()
        
        for current_node in current_nodes:
            visited_nodes.add(current_node)
            next_nodes |= graph[current_node]
        next_nodes -= visited_nodes
    
    return len(current_nodes)

BFS 방식으로 탐색을 진행하므로, 다음에 방문할 노드가 없다면, 현재 노드가 리프 노드이자 가장 먼 거리에 위치하고 있음을 알 수 있다.