Baekjoon-2176-합리적인 이동경로
05 Oct 2022나의 접근 방법: Dijkstra + DFS 로 접근해보려 했는데, 시간초과가 발생했다.
문제는 DFS였는데, Dijkstra를 2->1로 접근했기 때문에 distance tree로 생각하면 node 2를 root로 한다.
즉 DFS를 1을 root로 하면 distance tree 의 leaf 부터 올라오는 것이므로 훨씬 시간이 적게 걸린다.
반면 2를 root로 DFS를 실행하면, 모든 노드를 다보게 되므로 시간이 오래걸린다.
import sys
input = sys.stdin.readline
import heapq
N,M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
A,B,C = map(int, input().split())
graph[A].append((B,C))
graph[B].append((A,C))
# Dijkstra O(NlogN + M)
queue = [(0,2)]
dist_from_2 = [1e9] * (N+1)
dist_from_2[2] = 0
while queue:
cur_dist, node = heapq.heappop(queue)
if cur_dist > dist_from_2[node]: # 할 필요 없음 (이미 다른 곳에서 update 발생)
continue
for v,w in graph[node]:
new_dist = min(dist_from_2[node] + w, dist_from_2[v])
if new_dist < dist_from_2[v]:
dist_from_2[v] = new_dist
heapq.heappush(queue, (dist_from_2[v],v))
# DFS + DP O(M)
# Distance tree는 2를 root로 하기때문에 DFS를 1부터 searching 하는 것이 시간복잡도 면에서 훨씬 유리하다.
dp = [0] * (N+1)
dp[2] = 1
def dfs(u):
if dp[u]==0:
for v,w in graph[u]:
if dist_from_2[v] < dist_from_2[u]:
dp[u] += dfs(v)
return dp[u]
else:
return dp[u]
print(dfs(1))