[BOJ4196] 도미노

[BOJ2150] 도미노

문제 링크

문제 설명

• 도미노에 비유한 방향 그래프가 주어지고, 만약 a->b 로 그래프가 만들어질 경우, a를 넘어뜨리면 b도 넘어지는 방식으로 방향그래프를 통해 도미노를 만든다고 가정.

• 하나의 노드(블록)을 쓰러트렸을 때 연쇄적으로 연결된 노드(블록)이 쓰러진다.

• 이런 경우, 손으로 직접 쓰러트려야하는 노드(블록)의 최소 개수를 구하는 문제이다.

풀이 과정

• 같은 SCC(강한 연결 성분)끼리는 하나의 노드(블록)을 쓰러트리면, 다른 블록들도 모두 쓰러진다.

• 즉, 같은 SCC 끼리 하나의 노드로 취급하여 묶어준다면, 사이클이 없는 방향그래프 즉 DAG이 형성될 것이다.

• 그렇게 생긴 DAG에 대해 indegree가 0인 개수를 세면, indegree가 0이라는 말은 다른 노드에 의해 쓰러질 수 없다는 말이므로, 손으로 직접 쓰러트려야 된다는 말이 된다.

• 정리하자면, 주어진 방향그래프에 대해, SCC를 구하여 하나의 SCC를 하나의 노드로 생각한 후 만들어진 DAG에 대해 indegree가 0인 노드의 개수를 세면 된다.

코드

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;

vector <vector <int>> adj;
vector <int> scc_num;
stack <int> discover_stack;
int discover_time[100005];
int finish_time[100005];
int low_level[100005];
int color_check[100005];
int ind[100005];
int scc_group;
int time;

void scc_dfs(int v) {  //dfs를 통해 scc를 구하는 과정
	color_check[v] = 1;
	discover_time[v] = ++time;
	discover_stack.push(v);
	low_level[v] = discover_time[v];
	int size = adj[v].size();
	for (int i = 0; i < size; i++) {
		int w = adj[v][i];
		if (color_check[w] == 0) {
			scc_dfs(w);
			low_level[v] = min(low_level[v], low_level[w]);
		}
		else if (color_check[w] == 1) {
			low_level[v] = min(low_level[v], discover_time[w]);
		}
		else if (color_check[w] == 2) {
			if (discover_time[v] < discover_time[w]) continue;
			else if (discover_time[v] > finish_time[w]) {
				if (scc_num[w] != 0) continue;
				else {
					low_level[v] = min(low_level[v], low_level[w]);
				}
			}
		}
	}
	color_check[v] = 2;
	finish_time[v] = ++time;
	if (discover_time[v] == low_level[v]) {
		scc_group++;
		while (1) {
			int top_v = discover_stack.top();
			scc_num[top_v] = scc_group;
			discover_stack.pop();
			if (top_v == v) break;
		}
	}
}


int main() {
	int N, M, t;
	int ans=0;
	scanf("%d", &t);
	while (t--) {
		memset(discover_time, 0, sizeof(discover_time));
		memset(finish_time, 0, sizeof(finish_time));
		memset(low_level, 0, sizeof(low_level));
		memset(color_check, 0, sizeof(color_check));
		memset(ind, 0, sizeof(ind));
		ans = time = scc_group = 0;
		scc_num.clear();
		adj.clear();
		scanf("%d%d", &N, &M);
		scc_num.resize(N + 1);
		adj.resize(N + 1);
		for (int i = 0; i<M; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			adj[a].push_back(b);
		}
		for (int i = 1; i <= N; i++) {
			if (color_check[i] == 0) scc_dfs(i);
		}
		for (int i = 1; i <= N; i++) { //같은 scc에 대해 하나의 노드로 묶어 indegree 개수 체크
			int size = adj[i].size();
			for (int j = 0; j < size; j++) {
				int w = adj[i][j];
				if (scc_num[i] != scc_num[w]) ind[scc_num[w]]++;
			}
		}
		for (int i = 1; i <= scc_group; i++) if (ind[i] == 0) ans++;
		printf("%d\n", ans);
	}
	return 0;
}

코드 리뷰

• SCC의 개념에 대해 완벽히 알고있다면 충분히 풀 수 있는 문제라고 생각한다.

• indegree 개수를 헤아리는 부분에서 시간을 많이 잡아먹었다.

---