[Programmers] 가장 먼 노드

https://school.programmers.co.kr/learn/courses/30/lessons/49189

문제 정의

---

n개의 노드가 있고 간선에 대한 정보가 주어진다.

간선은 양방향이며, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 한다.

가장 멀리 떨어진 노드란? → 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다.

접근 방법

---

가장 멀리 떨어진 노드의 개수를 구하는데 최단 경로로 이동했을 때 가장 멀리 떨어진 노드이다.

따라서 가장 멀리 떨어진 노드까지 최단경로로 이동 했을 때 얼만큼 떨어져있는지?를 알아야 한다. 예를 들면 소요된 거리 또는 비용이라던가?

여기서는 간선에 대한 비용이 주어져있지 않으므로, 간선의 비용을 1로 설정해서 소요 비용을 구할 수 있다.

문제에서 최단경로라고 힌트를 주었기 때문에 ‘최단경로’인 다익스트라 알고리즘을 사용해서 풀 수 있다.

문제 해설

---

• 양방향 간선이라고 나와있으므로, 그래프에 양방향 간선에 대한 정보를 (도착노드, 거리) 로 저장해준다.

• 다익스트라 알고리즘을 구현한다.

• 최단거리 비용리스트인 distance에서 출발 노드인 1을 제외한 나머지 노드 중 가장 멀리 떨어진 노드가 몇 개 인지 찾아본다.
  • 가장 멀리 떨어진 노드 = 최단 거리가 가장 큰 노드

풀이

---

import heapq

def solution(n, edge):
    answer = 0
    
    graph = [[] for _ in range(n+1)]    # 그래프 연결 정보를 담은 리스트
    
    for e in edge:
        graph[e[0]].append((e[1], 1))
        graph[e[1]].append((e[0], 1))
    
    # [[], [(3, 1), (2, 1)], [(3, 1), (1, 1), (4, 1), (5, 1)], [(6, 1), (4, 1), (2, 1), (1, 1)], [(3, 1), (2, 1)], [(2, 1)], [(3, 1)]]
    
    INF = 1e9
    distance = [INF] * (n+1)   # 각 노드까지의 최단 거리
    distance[0] = 0
    
    q = []
    heapq.heappush(q, (0, 1))    # (거리, 노드)
    
    while q:
        d, now = heapq.heappop(q)
        if distance[now] < d: continue
        
        for i in graph[now]:
            cost = d + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    
    max_d = max(distance[2:])
    for i in range(2, n+1):
        if distance[i] == max_d:
            answer += 1
        
    return answer

정리

---

• 시간복잡도는 다익스트라 최단경로 알고리즘인 $O(ElogV)$ 이다.

• 다익스트라 알고리즘을 짤 수 있다면 쉬운 문제인 것 같다.

Uploaded by N2T