[백준문제풀이] 4196 도미노

 

풀이일시 : 2020-08-29

​

 

문제 :

도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다.

이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하자.

ex)

1

3 2

1 2

2 3

​

 

입력:

첫 번째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 도미노 블록의 번호는 1과 N 사이의 정수다. 다음 M개의 줄에는 각각 두 정수 x, y가 주어지는데, 이는 x번 블록이 넘어지면 y번 블록도 넘어짐을 뜻한다.

ex)

1

​

 

출력:

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 정답은 손으로 넘어뜨려야 하는 최소의 도미노 블록 개수이다.

​

 

풀이 :

SCC 사이의 관계까지 구해야 하는 문제로 이들의 관계는 위상정렬을 수행함으로 알 수 있다. SCC자체를 정점으로 보고 위상정렬을 수행했을때 진입차수(inDegree)가 0인 정점의 갯수를 세 주면 된다.

 

dbstndi6316.tistory.com/57

[기본문제풀이] 강한결합요소

dbstndi6316.tistory.com/56

[기본문제풀이] topology_sort

#include <iostream>
#include <stack>
#include <vector>

#define MAX 100001

using namespace std;

int n, m;
int id, d[MAX];
bool finished[MAX];
vector<int> a[MAX];
vector<vector<int> > SCC;
stack<int> s;
int group[MAX];
bool inDegree[MAX]; //각각의 정점의 진입차수가 몇인지 확인

int dfs(int x) {
	d[x] = ++id;
	s.push(x);
	int parent = d[x];
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		if (d[y] == 0)
			parent = min(parent, dfs(y)); //min이 안될경우 __min 또는 #define NOMINMAX 추가해주면됨
		else if (!finished[y]) //d[y]==0이 아니더라도 finished가 아니라면 가능
			parent = min(parent, d[y]);
	}
	if (parent == d[x]) { //min한 최소값(parent)이 처음값 d[x]와 같다면 즉 부모가 자신으로 돌아오면
		vector<int> scc; //scc선언
		while (1) {
			int t = s.top(); 
			s.pop(); //스택에서 꺼낸다.
			scc.push_back(t);
			group[t] = SCC.size() + 1; //특정한 SCC에 속해있는 모든 
			//정점들이 SCC크기에 1을 더해준값을 넣어주는것
			//첫번째 SCC에 들어있는 애들은 1값을 가질것이고
			//두번째 SCC에 들어있는 애들은 2값을 가질것이다.
			//그룹값을 기준으로 어떤 SCC에 포함되어있는지 구별할수있다.
			finished[t] = true;
			if (t == x)
				break;
		}
		SCC.push_back(scc); //만들어진 scc를 SCC에 넣는다.
	}
	return parent;
}

int main() {
	int t; //테스트케이스의 수
	scanf_s("%d", &t);
	while (t--) { //테스트케이스만큼 반복한다.
		SCC.clear();
		fill(d, d + MAX, 0); //d값을 초기화한다.
		fill(finished, finished + MAX, 0); //끝났는지 판별 초기화 0
		fill(inDegree, inDegree + MAX, 0); //진입차수 초기화 0
		scanf_s("%d %d", &n, &m); //정점과 간선정보
		for (int i = 1; i <= n; i++) {
			a[i].clear();
		}
		for (int i = 0; i < m; i++) {
			int x, y;
			scanf_s("%d %d", &x, &y);
			a[x].push_back(y); //x넘어뜨리면 y도 넘어진다.
		}
		for (int i = 1; i <= n; i++) {//모든 노드에 대해서 dfs
			if (d[i] == 0)
				dfs(i);
		}

        //위의 과정에서 scc에 의한 SCC가 전부 생성이 됐을 것이다.
		for (int i = 1; i <= n; i++) { //n:도미노의 개수
			for (int j = 0; j < a[i].size(); j++) { //i도미노에 연결된 도미노들을 순회하며
				int y = a[i][j]; //연결되어진 정점을 y로 함
				if (group[i] != group[y]) //y와 i가 속한 그룹이 다르다면
					inDegree[group[y]] = true; //y가 속한 SCC의 그룹 값을 true로 즉 진입차수가 존재한다.
			}
		}

		int result = 0;
		for (int i = 1; i <= SCC.size(); i++) { //SCC들을 확인하면서
			if (!inDegree[i]) //진입차수가 0인경우에만 (손으로 도미노를 넘기는경우)
				result++; //갯수 증가시킨다.
		}
		printf("%d\n", result);
	}
	return 0;
}