백준 2176 - 합리적인 이동경로

문제 설명

제한사항 및 입출력

풀이

문제가 굉장히 너무 간결하게 써있어서 직관적으로 이해하기 어려웠던 것 같다. S에서 시작하여 T로 이동하는데, 한 정점에서 다른 정점으로 이동할 때 목적지인 T에 더 가까워지며 이동하는 경우 이것을 합리적인 이동경로라고 한다.

-> 여기서 합리적인 이동경로에 대한 정의를 다시 내려보자면 u에서 v로 이동할 때 distance(u, T) > distance(v, T) 인 경우를 말한다.

이제 S에서 시작하여 T까지 도달하기까지 가능한 모든 합리적인 이동경로의 개수를 구하는 것이 문제이다.

 

일반적으로 주어진 격자에서 한 점에서부터 다른 점까지의 모든 최적 이동경로의 개수를 구하는 문제는 DP를 활용해서 풀이할 수 있다. DP로 풀이할 수 있는 이유는 DAG가 성립하기 때문이다.

(DAG란 Directed Acyclic Graph의 약자로 사이클이 없고 방향을 가진 그래프를 의미한다. DP의 성립 조건이 DAG인 이유는 원인(선행 값) -> 결과(후행 값)의 방향이 절대 되돌아가지 않아야 DP가 한 패스로 끝나기 때문이다. https://www.acmicpc.net/problem/1577 이 문제를 보면 "한 쪽 방향으로만 갈 수 있다"라는 설명은 없지만 "최단 경로로만 이동한다"라는 조건이 붙어있다. 해당 조건이 의미하는 것은 경로가 좌측 상단에서 우측 하단으로만 흐른다는 것을 의미한다. 따라서 각 지점을 노드로 보았을 때 사이클이 형성되지 않는다는 것을 알 수 있다.)

 

이 문제에서는 "이동할 때 T에 가까워진다"라는 설명이 DAG를 만족하는 그래프를 그릴 수 있게 해준다. 해당 문제에서 그래프는 방향을 갖지 않지만 가중치를 갖는다. 가중치가 있다면 한 지점에서 목적지까지의 최단거리를 찾을 수 있고, 이동할 때의 멀어진다, 가까워진다의 기준을 이 최솟값으로 판단할 수 있다.

 

정리하자면 다음과 같다.

1. 모든 지점으로부터 목적지의 최단거리를 구한다. -> 합리적인 경로를 판단하기 위함

2. 먼 거리부터 시작하여 목적지까지의 경로 계산

아래 코드를 확인해보자.

내 코드

from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.readline
mis = lambda: map(int, input().split())
INF = float('INF')

S, T = 1, 2

def dijkstra(graph, n):
    dis = [INF] * (n+1)
    dis[T] = 0
    
    heap = [(0, T)]
    while heap:
        dist, x = heappop(heap)
        
        if dis[x] < dist:
            continue
        
        for nx, w in graph[x]:
            cost = dist + w
            
            if cost < dis[nx]:
                dis[nx] = cost
                heappush(heap, (cost, nx))
    
    return dis
    
n, m = mis()
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = mis()
    
    graph[a].append((b, c))
    graph[b].append((a, c))
    
ans = 0
distance = dijkstra(graph, n)
order = sorted(range(1, n+1), key= lambda x: distance[x], reverse= True)   # T에서부터 먼 순

dp = [0] * (n+1)        # dp[i] = S에서 i까지 갈 수 있는 합리적 경로의 개수
dp[S] = 1
for i in order:
    if distance[i] == INF:     # distance[i]는 i부터 T까지 최단거리
        continue
    
    for j, _ in graph[i]:
        if distance[j] < distance[i]:     # i에서 j로 이동하는데 j부터 T까지의 최단거리가 더 작다면 더함
            dp[j] += dp[i]

print(dp[T])

위에서 말한 두 단계를 확인해보자.

1번 단계는 다익스트라를 통해 T지점으로부터 다른 모든 지점까지의 최단거리를 확보했다.

2번 단계는 먼 거리부터 시작하여 목적지까지의 경로 계산이다.

왜 먼거리부터 시작해야 하는가? 에 대한 답변은 DAG를 성립시키기 위한 조건이라고 했는데, 왜 먼 거리부터 시작해야 DAG를 성립할까? 이 문제를 그래프가 아닌 "격자판에서의 최단경로의 개수"로 생각해보면 이해가 쉽다. 먼 거리부터 고려하지 않는다면 격자의 뒤로 돌아가는 것과 같다. 이런 경우는 최단거리를 보장하지 않고 무한히 도는 상황이 발생할 것이다.

 

• 그래프 구성: O(n + m)
• 다익스트라(T에서 시작): 이진 힙 사용 → O(m log n)
• 거리 기준 정렬: O(n log n)
• DP 누적 루프(모든 간선 한 번씩 확인): O(m) (무방향이라 인접 리스트엔 2m개가 들어가지만 상수 배)

시간 복잡도: O(m log n)

고찰

다른 풀이는 생각나지 않는다. 최단거리를 찾는 알고리즘만 상황에 따라 다익스트라가 아닌 밸만포드, BFS등으로도 풀릴 것 같지만 현재 주어진 문제 조건에서는 다익스트라 + DP 조합이 최적의 알고리즘이라고 생각하고 문제 제출자의 의도인 것 같다. 다른 사람의 풀이를 확인해봐도 다른 방법은 찾아보지 못했다...