🔴 문제 개요
🚀 난이도 : GOLD 4
위와 같이 N 개의 정점이 모두 연결되도록 N-1 개의 간선이 주어질 때, 임의의 두 정점 a, b 에서 출발한 로봇이 서로 소통할 수 있도록 직접 연결되기 위해 이동해야 하는 이동 거리의 최솟값을 구하면 되는 문제입니다.
예를 들어 두 로봇이 1, 9 정점에서 출발한다면 연결되기 위해서 각각 2, 5로 이동하고, 이때의 이동거리 합은 14입니다.
제한 사항
- 모든 서브태스크에서 1 ≤ N ≤ 100,000이며, 통로의 길이는 1,000을 넘지 않는다.
🟠 Solution
이번 문제에서는 제가 제안하는 첫 번째 Solution과, 다른 분께서 풀이 하신 더 효율적인 두 번째 Solution을 공유해드리고자 합니다. 두 Solution은 Djikstra 알고리즘을 활용하였으며, 해당 알고리즘을 숙지하신 상태라고 가정하고 설명합니다.
1️⃣ Solution 1 : Djikstra + 간선 완전 탐색
첫 번째 솔루션은 제가 풀이한 방법입니다. 입력 과정에서 간선들의 정보를 모두 저장하고, 두 점 a, b에서 Djikstra 알고리즘을 통해 모든 지점까지의 최단 거리를 모두 확보합니다.
그럼 우리는 1과 5에서 다른 정점으로 이동하는 모든 경우를 완전탐색하면 a, b가 연결되는 지점까지 이동하는 최소 이동 거리를 찾을 수 있습니다. 이 때 a, b가 연결되려면 두 경우가 존재할 수 있겠죠
- a, b가 edge를 구성하는 각각 두 점으로 형성되는 경우
- a, b가 한 정점에서 만나는 경우
따라서 저장한 간선과 모든 노드를 차례대로 순회하면서 이동 거리를 계산하고, 그 중 최소인 경우를 출력하면 됩니다.
다익스트라 알고리즘의 시간 복잡도는 ElogV이고, 정점은 100,000개, 간선은 100,000-1개입니다.
다익스트라 2회 + 엣지 정방향 순회 + 엣지 역방향 순회 + 정점 순회가 필요하며,
N = 100,000으로 계산하면 최종 시간 복잡도는 대략 2NlogN + 3N 으로 해결 가능합니다.
import sys
from heapq import heappush, heappop
from typing import List
INF = 10e10
input = sys.stdin.readline
N, a, b = map(int, input().rstrip().split())
adj = [[] for _ in range(N + 1)]
edges = [] # 이후 엣지 순회를 위해 엣지 정보도 저장
# input : 인접리스트, 정방향 엣지, 역방향 엣지
for _ in range(N - 1):
u, v, w = map(int, input().rstrip().split())
adj[u].append((w, v))
adj[v].append((w, u))
edges.append((u, v))
edges.append((v, u))
def djk(st: int) -> List[int]:
"""
정점 st에서 다른 정점까지 이동하는 최소 거리를 반환한다.
"""
heap = [(0, st)]
dist = [INF for _ in range(N + 1)]
dist[st] = 0
while heap:
w, v = heappop(heap)
if dist[v] != w:
continue
for nxt_w, nxt_v in adj[v]:
cost = w + nxt_w
if cost < dist[nxt_v]:
dist[nxt_v] = cost
heappush(heap, (cost, nxt_v))
return dist
djk_a = djk(a)
djk_b = djk(b)
answer = INF
# 정점 순회
for node in range(1, N + 1):
tmp = djk_a[node] + djk_b[node]
if answer > tmp:
answer = tmp
# 엣지 순회
for st, en in edges:
tmp = djk_a[st] + djk_b[en]
if answer > tmp:
answer = tmp
print(answer)2️⃣ Solution2 : Djikstra + 최대 간선 활용
두 번째 Solution은 이 블로그의 풀이를 참고했습니다. a에서 b까지의 최단 경로에서 최대 엣지를 활용한 Solution 입니다.
위 경우처럼 주어지는 그래프는 a에서 b까지 연결된 하나의 경로가 제공됩니다. 즉, a에서 b까지 이동하는 경로는 정해져있으며, 그 최단 거리도 위와 같이 확정된 상태입니다.
이 때, 최대 길이의 간선을 알게 된다면 해당 간선을 건너지 않고 a, b가 각각 해당 간선 위에 존재할 때 가장 최소로 이동한 경우일 것입니다. 위 경우에서는 a는 2로 이동하고 b는 3으로 이동한 경우에 해당될 것입니다.
따라서, a에서 b까지 이동하는 최단 거리를 다익스트라(or DFS, BFS)로 확인한 다음 그 과정에서 해당 경로 상의 최대 길이의 간선을 구해 마지막에 빼주면 답을 도출할 수 있습니다.
이 경우 꼭 Djikstra 알고리즘을 활용하지 않아도 되며, Djikstra 알고리즘을 1회만 수행하고 그 과정에서 최대 간선을 저장하는 것 이외에 별 다른 과정이 필요 없으므로 더욱 효율적으로 문제를 해결할 수 있습니다.
Djikstra 알고리즘을 수행하는 과정에서 별도의 최대 간선 길이를 저장하는 리스트와 Heap을 활용하여 최대 간선의 길이를 구해냈습니다.
import sys
from heapq import heappush, heappop
INF = 10e10
input = sys.stdin.readline
N, a, b = map(int, input().rstrip().split())
adj = [[] for _ in range(N + 1)]
dist = [INF for _ in range(N + 1)] # 각 지점까지의 최단 거리
max_dist = [0 for _ in range(N + 1)] # 해당 경로에 포함된 최대 간선 길이
for _ in range(N - 1):
u, v, w = map(int, input().rstrip().split())
adj[u].append((w, v))
adj[v].append((w, u))
def djk(st: int) -> None:
heap = [(0, st, 0)]
dist[st] = 0
while heap:
w, v, md = heappop(heap)
if dist[v] != w:
continue
for nxt_w, nxt_v in adj[v]:
cost = w + nxt_w
if cost < dist[nxt_v]:
dist[nxt_v] = cost # 최단 거리 업데이트
max_dist[nxt_v] = max(nxt_w, md) # 최대 간선 업데이트
heappush(heap, (cost, nxt_v, max_dist[nxt_v])) # 힙에 같이 push
djk(a)
print(dist[b] - max_dist[b]) # 최소 경로 길이 - 최대 간선 길이
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
