문제 풀이/백준 (BOJ)
[백준/BOJ] 4196번: 도미노 ( 코사라주 Kosaraju 알고리즘 응용 ) - C++ 문제 풀이
문제 설명 문제 링크: https://www.acmicpc.net/problem/4196 풀이이 문제는 최소 몇 번을 손대야 모든 도미노를 쓰러뜨릴 수 있는지를 출력하는 문제입니다. 이 문제를 처음 맞닥뜨렸을 때, 가장 먼저 떠오르는 것은 깊이 우선 탐색이나, 너비 우선 탐색일 수 있습니다.예를 들어, 깊이 우선 탐색으로 방문이 가능한 정점들을 한 부분집합으로 만들면, 이 집합은 손짓 한 번으로 모두 쓰러뜨릴 수 있습니다.이렇게 해서, 부분 집합의 개수를 구하면 되는 문제 같습니다. 그러나, 다음 예제를 보면 조금 다른 과정이 필요한 것을 알 수 있습니다. 이 그래프는 1번 정점부터 깊이 우선 탐색을 하면, { 1, 2, 3 }과 { 4 } 탐색 이렇게 두 번의 탐색 과정이 필요합니다.그러나, 4번 정점..
2024. 7. 15.
