백준 4196 도미노 C++
https://www.acmicpc.net/problem/4196 SCC를 활용한 문제입니다. 도미노 관계가 주어졌을 때, 최소 몇 개의 도미노를 넘어트려야 전체 도미노가 쓰러지는 지를 계산합니다. SCC를 계산하면, 각 SCC는 사이클을 이루므로 아무거나 넘어트려도 됩니다. 그리고 SCC를 구성하는 컴포넌트들을 하나의 큰 노드로 본다면, 그 노드들 중 indegree 엣지가 0인 것들만 넘어트린다면 전체가 넘어지고, 이것이 최소 개수입니다. indegree 엣지가 0인 것들은, 입력된 그래프의 엣지를 대상으로, from, to 노드가 동일 컴포넌트인지 아닌지를 체크하면 알 수 있습니다. 즉, 컴포넌트 번호가 다르다면, 엣지로 연결된 두 노드는 다른 컴포넌트에 있는 것이고, 이는 to 노드가 포함..
알고리즘/백준
2025. 2. 20. 23:54