백준 4196 - 도미노(C++)

문제 링크입니다. https://www.acmicpc.net/problem/4196

4196번: 도미노

SCC(강한 연결 요소) 알고리즘을 이용해 위상정렬로 푸는 문제였습니다.

• 참고한 SCC 알고리즘 설명

https://hyeo-noo.tistory.com/m/130

강한 연결 요소 (SCC) - 타잔 알고리즘

• 추가로 참고할만한 SCC 알고리즘 내용

https://coder-in-war.tistory.com/m/entry/%EA%B0%9C%EB%85%90-56-SCCStrongly-Connected-Component

[ 개념 ] 56. SCC(Strongly Connected Component)

SCC를 찾기 위해서 타잔 알고리즘을 사용했습니다.

도미노는 자신 앞의 도미노가 넘어질 때 자신도 넘어지게 됩니다.
-> 어떤 도미노가 무너지면 다른 도미노에게도 영향을 미친다.
-> X번 도미노에서 출발하면 X번과 연결된 도미노는 모두 무너진다.
-> 따라서 SCC 알고리즘을 사용하면 어떤 도미노들이 무너짐을 알 수 있다.


SCC 알고리즘은 서로 왕복 가능한 정점들만 찾아주지만, 도미노는 그렇게 움직이지 않습니다,
왕복하지 않더라도 연결만 되어 있다면 다른 SCC들까지 영향을 미칩니다.

예를 들어보겠습니다.
1 -> 2
2 -> 4
3 -> 1
4 -> 1
5 -> 3
위와 같이 연결이 되어있다면, SCC는 총 3개입니다. (1, 2, 4), (3), (5)가 됩니다,
그렇다면 3개를 넘어뜨리면 되냐? -> 아님을 알 수 있습니다.
5번 하나만 넘어뜨리면 전부 넘어짐을 알 수 있습니다.


따라서, SCC의 갯수만을 구하는 것이 아닌, SCC 각각의 연결 관계를 확인한 뒤, 시작의 SCC를 넘어뜨리면 됨을 알 수 있습니다.
-> 위상 정렬의 방법이 여기서 사용됩니다.

SCC의 연결 관계는 입력 당시에 어떤 도미노들이 연결 되었는지를 알려주며, 어떤 도미노들이 몇번의 SCC인지 알고 있습니다.
이를 이용해 step값이 0인 SCC의 갯수를 찾아주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#define F first
#define S second

using namespace std;

int test_case;
int N, M;
vector<int> connect[100001];

int SCC_step[100001]; // SCC의 딘계를 저장
int SCC_id[100001]; // 각 도미노의 SCC 번호를 저장
int check[100001]; //
int SCC_cnt, vertex_cnt; // SCC가 몇개인지, 몇번째 방문 순서인지
vector<int> stk;

void reset_array(){
	for(int i = 0; i <= N; i++){
		connect[i].clear();
		SCC_step[i] = 0;
		SCC_id[i] = -1;
		check[i] = -1;
	}
	SCC_cnt = 0;
	vertex_cnt = 0;
}

int SCC(int start){ // SCC를 구한다.
	int ret = check[start] = vertex_cnt++;
	stk.push_back(start);
	for(int i = 0; i < connect[start].size(); i++){
		int next = connect[start][i];
		if(check[next] == -1){
			ret = min(ret, SCC(next));
		}
		else if(SCC_id[next] == -1){
			ret = min(ret, check[next]);
		}
	}
	if(ret == check[start]){
		while(1){
			int x = stk.back();
			stk.pop_back();
			SCC_id[x] = SCC_cnt;
			if(x == start) break;
		}
		SCC_cnt++;
	}
	return ret;
}

void solve(){
	int result = 0;
	for(int i = 1; i <= N; i++){
		if(check[i] != -1) continue;
		SCC(i);
	}
	for(int i = 1; i <= N; i++){
		for(int j = 0; j < connect[i].size(); j++){
			int next = connect[i][j];
			if(SCC_id[i] == SCC_id[next]) continue;
			// i번 도미노를 넘겼을 때 next도 넘어진다면
			// i번 도미노의 SCC는 next의 SCC의 이전 단계인 것이다.  
			SCC_step[SCC_id[next]]++;
		}
	}
	for(int i = 0; i < SCC_cnt; i++){
		// 결국 0의 값을 가진 SCC를 넘기기만 하면 모든 도미노는 넘어진다.
		if(SCC_step[i] == 0) result++;
	}
	cout << result << "\n";
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for(int k = 1; k <= test_case; k++){
		cin >> N >> M;
		reset_array();
		for(int i = 1; i <= M; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			connect[x].push_back(y); //도미노의 관계를 저장
		}
		solve();
	}
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.