Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 가장 먼 노드

[가장 먼 노드]

Solution. BFS $O(V+E)$

from collections import deque

def bfs(n, adj, v):
    queue = deque([v])
    dist = [None]*(n+1)
    dist[v] = 0
    mx = 0

    while queue:
        cur = queue.popleft()
        for nxt in adj[cur]:
            if dist[nxt] is None:
                dist[nxt] = dist[cur]+1
                if mx < dist[nxt]: mx = dist[nxt]
                queue.append(nxt)
    
    return dist.count(mx)

def solution(n, edge):
    adj = [[] for _ in range(n+1)]
    for u, v in edge:
        adj[u].append(v)
        adj[v].append(u)

    return bfs(n, adj, 1)

• 가중치가 없는 그래프이기 때문에 BFS로 풀 수 있다.
• 방문 처리를 None과 Not None(0, 1, 2...) 으로 하여 방문 처리와 1번 노드와의 거리를 하나의 리스트로 관리했다.
• 각 노드를 순회하며 거리의 최댓값을 갱신해 나가고, BFS가 종료되면 해당 값이 dist에 몇 개 존재하는지 센다(1번 노드에서 가장 멀리 떨어진 노드의 수를 센다).

---