고수는 아니지만, 개인적인 의견을 적어보자면 상향식과는 달리, 하향식으로 하려면 이미 검토한 노드를 다시 검토해야 하는 문제가 생깁니다. 문제의 예시만 해도 그런 문제가 나오는데요, 4->2를 한 후, 2->1을합니다. 이후, 4->3, 3->1을 하는데, 이 과정에서 1번 건물을 2번 확인해야 합니다. 상향식에서와 달리 하향식으로 dfs나 bfs를 할 경우에는 1번 건물이 이미 visited 처리가 되어서 다시 검토되질 못합니다. 이런 문제점에 대한 해결만 가능하다면 하향식도 충분히 가능합니다. 그런데, 굳이 추가적인 문제를 만들어가면서까지 하향식을 하려는 사람은 없을 것 같네요...
dohoon 3년 전
위상정렬로 풀 수 있다는 것은 알고 있습니다.
그런데 풀다보니까,
위상정렬을 위해 주어진 간선들의 방향을 정반대로 바꾸고, 하향식 DP를 진행한다면..?
결국 그 두 가지 풀이는 동치가 아닌가 라는 생각이 들었습니다.
그래서 저는 하향식 DP를 시도해보았습니다.
일단 이 문제에 대해 proof by AC를 했습니다.
제 생각을 검토해주실 고수 분들 구합니다..!