그래프 방향 확인
간선이 상태 전이를 어느 방향으로 밀어야 하는지 문제 문장과 맞춘다.
역방향으로 풀면 base case가 뒤집힌다위상 순서 생성
indegree를 쓰는 Kahn 방식이나 DFS 종료 순서로 사이클 없는 순서를 만든다.
방문 수가 N보다 작으면 사이클을 의심한다초기값 배치
시작점만 0 또는 1로 두고 도달 불가 노드는 INF나 0 등 의미 있는 값으로 남긴다.
모든 노드 0 초기화가 항상 맞지는 않다전이 적용
위상 순서대로 u를 꺼내 모든 u->v 간선에 대해 dp[v]를 갱신한다.
선행 상태가 먼저 계산되어 있다는 전제가 핵심이다결과 범위 선택
특정 도착점인지, 모든 노드 중 최대/최소인지, 도달 가능한 노드만 보는지 결정한다.
도달 불가 값을 답에 섞지 않는다Cycle
위상 순서 불가
Kahn 처리 개수가 노드 수보다 적으면 DP 전제가 깨진다.
문제가 DAG 보장인지 입력 검증이 필요한지 본다
Initial
시작 상태 의미
경우의 수, 거리, 길이에 따라 0, 1, INF 초기값이 달라진다.
base case가 전이보다 먼저다
Unreachable
도달 불가 제외
갱신되지 않은 상태를 다음 전이에 쓰지 않도록 조건을 둔다.
INF + weight overflow도 조심한다
Order
선행 계산 보장
위상 순서가 아닌 순회는 아직 모르는 dp 값을 사용하게
만든다.
간선 방향과 순서를 함께 점검한다