SCC (1) 썸네일형 리스트형 백준 4196 - 도미노 https://www.acmicpc.net/problem/4196 힌트 더보기 도미노를 그래프로 모델링하면 위상 정렬을 통해 진입 차수가 0인 노드의 개수를 세는 방법으로 접근할 수 있다. 하지만 이것으로는 부족하다. 도미노의 상태에 따라 사이클이 생성될 수도 있고 그렇지 않을 수도 있다. 다음 그래프를 보자. 여기서 좌상단에 있는 사이클의 아무 도미노나 넘어트리면 모든 도미노를 넘어뜨릴 수 있다. 사이클을 영리하게 이용하는 방법을 생각해본다. 풀이 더보기 최소한의 시행으로 모든 도미노를 넘어뜨리기 위해서는 indegree가 0인 도미노만 건드려야 한다. 하지만 위에 힌트에서도 언급했듯이 어떤 도미노 집합이 사이클을 이루고 있는 경우에는 indegree가 0인 도미노가 없지만 해당 사이클에서 아무 도미노.. 이전 1 다음
