DP는 DAG에 대해서만 사용해야 합니다. 이 문제처럼 정점의 방문 선후 관계가 명확하지 않은 경우에는 사이클에 의해 잘못된 답을 구할 수 있게 됩니다.
1697번 - 숨바꼭질
사이클에 들어가려고 하는 경우엔 1e9 반환으로 고려하지 않도록 하였습니다. 그렇다면 이 경우는 사이클이 존재하지 않는 것(acyclic) 아닌가요?
이런 경우를 생각해 보세요. 답이 되는 경로를 찾으려면 a - b 순으로 거쳐가야만 되는 상황입니다. 그런데 만약 dfs의 탐색 순서가 a를 방문하기 전에 b를 먼저 방문했다고 칩시다 (실제로 시작점으로부터 a를 안 거치고 b에 도달하는 경로는 매우 멀다고 가정). 그러면 b에서 a를 방문한 뒤에, a에서 다시 b로 가는 경로를 탐색해야 하는데, 현재 경로에서는 이미 b를 한 번 거쳤기 때문에 여기서 1e9가 반환되어 "a에서 도착점까지 가는 최적의 경로는 b를 거쳐가는 것이다"라는 정보를 얻을 수 없게 됩니다. 이후에는 a의 dp값이 이미 결정되었기 때문에 b를 안 거치고 a를 먼저 방문하는 경로를 탐색하더라도 이후 b를 거쳐가는 경로를 고려할 수 없게 됩니다.
이야 명쾌하시네요. 많이 배워갑니다^^
댓글을 작성하려면 로그인해야 합니다.
akdlzmf6979 4년 전
DP로 풀었구요 언니의 위치 중 중복되는 경우는 전부 무시할 수 있도록 구현했는데요.
63%에서 자꾸 틀렸다고 나옵니다ㅜㅜ 제가 뭘 잘못했을까요?