[알고리즘 고득점 Kit] 그래프 - 가장 먼 노드

문제 풀이

1. 모든 경우를 봐야하므로 노드를 양방향으로 연결해 줍니다
2. BFS는 대충 deque에 시작점을 넣고 시작하면 편합니다
3. dist라는 배열을 만들고 -1로 값들을 초기화 합니다(이 값들이 시작점으로 부터의 거리가 되어 줄 것임)
4. connect 배열을 모두 탐색하며 bfs를 돌려줍니다
   • 모든 노드들이 1과 연결되어 있으므로 방문하지 않은 dist의 값들은 바로 전 값 + 1이 됩니다.
   • print(dist)를 찍어보시면 이해가 더 쉽습니다.
   • 큐를 모두 돌고 난 뒤 max(dist)를 찾고, 몇개나 나왔는지 count 하면 가장 먼 노드들이 몇 개인지 나오게 됩니다.

from collections import deque

def solution(n, edge):
    # 양방향 연결
    connect = [[] for _ in range(n+1)]
    for a, b in edge:
        connect[a].append(b)
        connect[b].append(a)

    # BFS
    dist = [-1] * (n+1)
    q = deque([1])
    dist[1] = 0

    while q:
        node = q.popleft()
        for nxt in connect[node]:
            if dist[nxt] == -1:   # 방문한 적 없으면
                dist[nxt] = dist[node] + 1
                q.append(nxt)

    # 가장 먼 거리 찾기
    max_dist = max(dist)
    return dist.count(max_dist)