Jae-Kyung Cho LLM Developers who was a Robotics engineer

Baekjoon-2176-합리적인 이동경로

나의 접근 방법: 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))
Comments