- 시간 제한: 1초
- 메모리 제한: 256MB
Problem Analysis
이러한 상황이 있을 때, 빨간색으로 체크한 부분을 넘어뜨려야 한다. Topological Order 순으로 넘어뜨리면 된다.
Algorithm
- Topological Sort를 한다.
- Topological order를 하나씩 pop 하면서, 넘어지지 않은 블록(visited==false)일 시 DFS로 인접 블록들을 넘어뜨린다(visited==true)
- DFS를 시행한 횟수가 곧 블록을 손으로 넘어뜨린 횟수이다.
Data Structure
- stack topological_Order:
- adjList
- visited
결과
Other
시간 복잡도는 O(V+E)이다.