백준 9466 텀 프로젝트

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

그래프 탐색과 DFS의 혼종이다.

 

그래프에 Cycle이 있는지 점검하는 문제다. 

 

무식하게 풀자면

 

모든 노드를 DFS 돌려서 자기 자신으로 돌아오는 지 체크하면 된다!

 

근데 중복이 엄청 많을 것이다. 아무리 시간 복잡도가 3초라도 이런건 무조건 시간초과다

 

메모이제이션을 통해 최대한 중복 체크를 줄인다!

 

각 노드의 상태는 둘로 나뉜다.

 

1. 이전 DFS에서 방문한 노드 - Cycle 못 만든다. 

2. 이번 DFS에서 방문한 노드 - Cycle 성립

3. 한번도 방문된 적 없는 노드 - Cycle이 될 지 안 될지 모른다. 

 

자세한 건 밑의 코드를 참고하시라~

 

노드를 방문할 때마다 방문 체크를 하고, 이미 방문한 적이 있는 노드면 그 방문이 이전 DFS인지 이번 DFS인지 따져서 

Cycle이 만들어지는지 만들어지지 않는지 return 한다.

 

핵심함수는 void dfs()이다.

/* 텀 프로젝트 */

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

using namespace std;

void input();
void solve();
void init();

int t_case, n_of_student;
vector<int> pick_the_student;
vector<pair<int, int>> history_of_visit;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> t_case;

	for (int i = 0; i < t_case; i++) {
		init();
		input();
		solve();
	}


	return 0;
}

void init() {
	pick_the_student.clear();
	history_of_visit.clear();
}

void input() {
	cin >> n_of_student;
	pick_the_student.resize(n_of_student + 1);
	history_of_visit.resize(n_of_student + 1, { 0, 0 });

	for (int i = 1; i <= n_of_student; i++) {
		cin >> pick_the_student[i];
	}
}

int dfs(int st, int day) {
	stack<int> s;
	s.push(st);

	history_of_visit[st].second = 1; // 이번 DFS에서 방문한 노드인지 체크한다. 
	history_of_visit[st].first = day; // 이전 DFS에서 방문한 노드인지 체크한다. 
	
	while (!s.empty()) {
		int current_node = s.top();
		int current_node_weight = history_of_visit[current_node].second;
		s.pop();

		int next_node = pick_the_student[current_node];
	
		// 이전 DFS에서 방문했다.
		if (history_of_visit[next_node].first != 0 && history_of_visit[next_node].first != day){ // 다른 DFS에서 방문한 노드라면
		
			return 0; // 팀 만들기 실패
		}
	
		if (history_of_visit[next_node].first== day) {// 이번 DFS에서 방문된 노드라면 
			current_node_weight = current_node_weight - history_of_visit[next_node].second + 1;
			return current_node_weight;
		}

		history_of_visit[next_node].first = day;
		history_of_visit[next_node].second = history_of_visit[current_node].second + 1;
		s.push(next_node);
	}
}

void solve() {
	// 각 노드마다 DFS를 돌려서 나로 돌아올 수 있는 지 체크한다. 
	int sum = 0, cnt = 1;
	for (int i = 1; i <=n_of_student; i++) {
		if (history_of_visit[i].first == false) {
			sum += dfs(i, cnt++);
		}
	}

	cout << n_of_student - sum << '\n';
}