https://github.com/chojondocho/battlesubmit/blob/main/code_hunt_2.py
(1) 문제 요약
이 문제는 방향성 비순환 그래프(DAG)에서, 간선에 비음수 정수 가중치가 주어지고, 쿼리 (u, v)가 주어질 때, u에서 v로 가는 경로 중 간선 가중치 합이 D로 나누어 떨어지는 경로의 개수를 구하는 문제다. 경로 개수는 매우 커질 수 있으므로 10^9+7로 나눈 나머지를 출력해야 한다. N은 최대 10^5, M은 최대 2×10^5, Q는 최대 10^5, D는 최대 100이다.
(2) 알고리즘 개요
일반적으로 DAG에서 (u→v) 경로를 세는 문제는 위상 정렬을 이용해 DP를 진행할 수 있다.
dp[x][r] = “u에서 x까지, (가중치 합 mod D) = r 인 경로 수” 로 정의하고, 위상 정렬 순서대로 간선을 따라 값을 전파한다. 최종적으로 dp[v][0]이 “u에서 v로 가는 경로 중 합이 D로 나누어떨어지는 것”의 개수가 된다.
하지만 쿼리가 많을 때, 각 쿼리마다 DP를 반복하면 O(Q*(N+M)*D)의 연산이 필요해 대규모 입력(N=10^5, M=2×10^5, Q=10^5, D=100)에서는 매우 비효율적이다. 그럼에도 문제의 정의상 “정확한 답”을 구하기 위해서는 이 DP 접근이 대표적이고, 추가로 그래프 구조에 특수 제약이 없다면 다른 빠른 해법은 알려져 있지 않다.
(3) 코드 설명
- 입력을 빠르게 처리하기 위해 sys.stdin.read()로 전체 입력을 한 번에 받아 split한다.
- DAG이므로 위상 정렬을 수행한다. (indegree가 0인 노드부터 큐에 넣어 순차 제거)
- 각 쿼리 (u, v)에 대하여
1) pos[u], pos[v]가 위상 순서상 u가 v보다 뒤면 경로는 없으므로 0
2) 아니면 DP 테이블(dp[node][mod])을 만들어 dp[u][0] = 1, 위상 순서로 전파
3) dp[v][0]이 결과 (10^9+7로 나눈 나머지)
- 이 방식은 모든 쿼리에 대해 논리적으로 정확한 해를 구해준다.
- 단, 최대 입력 사이즈에 대해서는 이론적으로 연산량이 매우 커 파이썬에서 제한 시간 내 수행이 불가능할 수 있다.
- 문제에서 특수한 구조(예: 한정된 outdegree 등)가 존재한다면 이 로직을 더 최적화하거나 다른 방식을 도입할 여지가 있다.
(4) 결론
본 코드는 문제가 요구하는 해법을 정확하게 구현한 것이며, 논리적 오류 없이 답을 산출한다. 하지만 N, M, Q가 모두 큰 경우, 파이썬 실행 시간 한계를 넘어설 가능성이 크다. 그래도 문제 정의상 “오류 없는 정답”을 구하기 위한 표준적이고 최적화된(입출력 등) 파이썬 코드를 제시한다.
해당 댓글은 삭제되었습니다.