[Programmers] Level 3. 가장 먼 노드

🔗 Problem Link

프로그래머스

---

❔Thinking

• 1부터 시작하여 연결된 노드 중 가장 먼 거리의 노드의 개수를 반환한다.

---

💻Solution

from collections import deque
def solution(n, edge):
    graph = [[] for i in range(len(edge)+1)]
    distance = [-1] * (n+1)
    # 그래프 연결하기
    for e in edge:
        start, end = e
        graph[start].append(end)
        graph[end].append(start)
        
    # 거리 초기화
    distance[1] = 0
    
    # 1번 노드에서의 거리 확인
    q = deque([1])
    while q:
        now = q.popleft()
        for i in graph[now]:
            if distance[i] == -1:
                q.append(i)
                distance[i] = distance[now] + 1
    return distance.count(max(distance))

---

🗝️keypoint

1. 정해진 노드에서 가장 먼 거리의 노드는, 각 노드까지의 거리가 가장 큰 값이다.
2. BFS와 distance를 활용하여 각 노드까지의 거리를 확인할 수 있다.