[프로그래머스] 가장 먼 노드

def dist_bfs(adj_matrix):
    from collections import deque
    visited = set()
    queue = deque([1])
    dist_list = [50001 for x in range(len(adj_matrix))]
    dist_list[0] = 0
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue += adj_matrix[node] - visited
            for x in adj_matrix[node]:
                dist_list[x-1] = min(dist_list[x-1], dist_list[node-1]+1)
    return dist_list
 
def solution(n, edge):
    adj_matrix = {key : set() for key in range(1,n+1)}
    for a,b in edge:
        adj_matrix[a].add(b)
        adj_matrix[b].add(a)
    dist_list = dist_bfs(adj_matrix)
    
    max_dist = max(dist_list)
    answer = 0
    for x in dist_list:
        if x == max_dist:
            answer += 1
    return answer

여기서 주의해야할 점은 매우 빈번히 연산되는 visited를 set으로 해야한다는 점이다.

파이썬 내부적으로 list가 set보다 iteration에서는 빠르지만

탐색(in함수)에서는 set이 훨씬 빠르다.