가장 거리가 먼 노드의 갯수

가장 거리가 먼 노드의 갯수

from collections import deque

def solution(n, edge):
    graph = [[] for _ in range(n)]
    for e in edge:
        graph[e[0]-1].append(e[1]-1)
        graph[e[1]-1].append(e[0]-1)

    distances = [-1] * n  # 최단 거리를 저장할 리스트
    distances[0] = 0  # 시작 노드의 최단 거리는 0

    q = deque([0])
    while q:
        curr = q.popleft()
        for neighbor in graph[curr]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[curr] + 1
                q.append(neighbor)

    max_distance = max(distances)
    answer = distances.count(max_distance)

    return answer

위의 코드에서 가장 중요한 부분은 가중치가 모두 동일한 그래프에서는 bfs 를 사용하는 것이 가장 효훌적이라는 점을 생각하는것이였다
또 중요한 부분은

distances[neighbor] = distances[curr] + 1

이 부분이라고 생각한다 나는 막혔던 부분이 바로 bfs 를 도는데 어디까지가 같은 거리인지를 구분하는 코드를 생각했었는데 그 전 노드들의 거리를 기록하고 현재 큐에 넣을 때 전의 노드 거리 +1 을 하는 방식이 생각이 존나 안났다 ...ㅎ