[코딩테스트 준비] 골드 1문제 (2176 합리적인 이동경로)

그래프의 정점 1(S)에서 정점 2(T)로 이동한다.
이동할 때마다 항상 정점 2에 더 가까워지는 방향으로만 이동하는 경로를
“합리적인 이동경로”라고 정의한다.

그래프가 주어질 때, 가능한 합리적인 이동경로의 개수를 구하는 문제다.

 

핵심 관찰

“정점 2에 더 가까워진다”는 말은
정점 2까지의 최단거리 값이 매 이동마다 감소해야 한다는 의미다.

따라서 각 정점에서 정점 2까지의 최단거리를 먼저 알아야 한다.

 

전체 풀이 전략

1. 정점 2에서 다익스트라 수행

• 정점 2를 시작점으로 다익스트라를 실행한다.
• dist[v] = 정점 v에서 정점 2까지의 최단거리

이 값이 이후 이동 가능 여부 판단 기준이 된다.

 

2. DFS + DP로 경로 개수 계산

• dp[u] = 정점 u에서 정점 2까지 갈 수 있는 합리적인 경로의 수
• 종료 조건
  • u == 2이면 1 반환
• 이동 조건
  • u -> v로 이동 가능 ⇔ dist[v] < dist[u]

최단거리 값이 항상 감소하므로, 순환이 발생하지 않아 DP가 가능하다.

 

알고리즘 정당성

• 합리적인 이동경로는 최단경로일 필요는 없지만
• 항상 “정점 2 기준 거리 감소” 조건을 만족해야 한다
• 다익스트라로 거리 기준을 고정한 뒤
• 그 기준을 만족하는 방향으로만 DFS를 수행하면
  모든 가능한 합리적인 경로를 중복 없이 셀 수 있다