간선 방향 정의
선행 상태에서 후행 상태로 간선이 향하도록 모델링한다.
DAG DP는 점화식보다 계산 순서 검증이 먼저다
위상 순서가 완성되지 않으면 아직 확정되지 않은 값을 참조하게 됩니다. 전이는 사이클 검증 뒤에 시작해야 합니다.
위상 정렬
처리 노드 수가 전체와 같은지 확인해 사이클을 걸러낸다.
초기값 고정
최장, 최단, 경로 수마다 도달 불가 값을 다르게 둔다.
전이 수행
위상 순서대로 max, min, sum 중 문제 요구에 맞게 갱신한다.
최장 경로NEG_INF에서 시작하고 max 전이로 갱신한다.
경로 수시작점을 1로 두고 후속 노드에 누적한다.
경로 복원값뿐 아니라 부모 선택을 별도로 저장한다.
DAG DP의 반례는 보통 사이클, 고립 노드, 다중 시작점에서 나옵니다. 위상 순서 길이와 초기 상태를 로그로 남기면 디버깅이 빨라집니다.