4196. 도미노

smsh0722·2022년 4월 22일
0

Graph

목록 보기
18/20

문제

  • 시간 제한: 1초
  • 메모리 제한: 256MB

Problem Analysis

이러한 상황이 있을 때, 빨간색으로 체크한 부분을 넘어뜨려야 한다. Topological Order 순으로 넘어뜨리면 된다.

Algorithm

  1. Topological Sort를 한다.
  2. Topological order를 하나씩 pop 하면서, 넘어지지 않은 블록(visited==false)일 시 DFS로 인접 블록들을 넘어뜨린다(visited==true)
  3. DFS를 시행한 횟수가 곧 블록을 손으로 넘어뜨린 횟수이다.

Data Structure

  • stack topological_Order:
  • adjList
  • visited

결과

Other

시간 복잡도는 O(V+E)이다.

profile
Military service - May 31, 2022 ~ Nov. 30, 2023

0개의 댓글