노드사이의 거리 ( 1240 번 )

1240번: 노드사이의 거리

 

---

🧠 알고리즘

• 다익스트라 알고리즘 (Dijkstra’s Algorithm, 최소 힙 기반)

 

✔️ 동작 방식

• 인접 리스트(conn_dict)로 트리의 연결 정보를 저장한다.
• 각 질의(a, b)에 대해, 최소 힙(우선순위 큐)에 (비용, 노드)를 넣어 탐색 시작.
• 힙에서 현재 비용이 가장 작은 노드를 꺼내고, 해당 노드의 인접 노드들을 확인한다.
• 목표 노드(end)에 도달하면 그 시점의 비용(now_cost)을 반환한다.
• 모든 질의에 대해 위 과정을 반복하여 결과를 출력한다.

---

 

🧾 코드

import sys, heapq

def _min_len(n, start, end, conn_dict):
    hq = []
    visit = [False] * n # 방문 체크
    visit[start - 1] = True
    heapq.heappush(hq, (0, start))

    while hq:
        now_cost, now_point = heapq.heappop(hq)
        
        if now_point == end:
            return now_cost

        for next_point, next_cost in conn_dict[now_point]:
            if visit[next_point - 1] is False: # 미방문 경우
                result_cost = now_cost + next_cost
                heapq.heappush(hq, (result_cost, next_point))
                visit[next_point - 1] = True
    

def _main(n, m):
    answer = []
    conn_dict = {i: [] for i in range(1, n + 1)}
    
    for _ in range(n - 1):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        conn_dict[a].append((b, c))
        conn_dict[b].append((a, c))

    for _ in range(m):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        answer.append(str(_min_len(n, a, b, conn_dict)))

    return '\n'.join(answer)

n, m = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, m))

---

 

⏱️ 시간 복잡도

for _ in range(m) : 질의 갯수 ( 선형 시간 복잡도 )
    _min_len(n, a, b, conn_dict)) : 다익스트라 알고리즘, 최소힙 기반 ( 선형 로그 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 이차형 로그 시간 복잡도 ( O(n ** 2 log n) )