[사이클 탐색] 방향 그래프, DFS로 해결 / 예제 문제: 텀 프로젝트_백준

예제 문제: 텀 프로젝트_백준

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

---

풀이

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int T, N;

int DFS_checkCycle(int node, vector<bool>& visited, /*vector<int>& groupVisited*/ map<int, int>& group, int groupMemberCnt, const vector<int>& Want) {
	// 종료 조건
	
	// 탐색
	int nextNode = Want[node];
	
	//if (groupVisited[nextNode] != -1) {
	if(group.find(nextNode) != group.end()) {
		// 그룹 생성
		// 최종 그룹 멤버 수 = groupMemberCnt - group[nextNode]
		return groupMemberCnt - (groupMemberCnt - group[nextNode]);
	}
	else if (visited[nextNode]) {
		// 그룹 생성 x
		return groupMemberCnt;
	}

	visited[nextNode] = true;
	group.insert({nextNode, groupMemberCnt}); 
	return DFS_checkCycle(nextNode, visited, group, groupMemberCnt + 1, Want);
}

int solution(const vector<int>& Want) {
	/*
	* DFS를 활용한 사이클 탐색 풀이
	* 그래프는 "방향 그래프"
	*/
	
	int cnt = 0;	// 팀이 없는 학생들의 수 카운트

	// 이미 탐색한 노드는 탐색하지 않기 위해 visited 배열 사용
	vector<bool> visited(N + 1, false);
	
	// 한명 씩 탐색을 시작
	for (int i = 1; i <= N; i++) {

		int node = i;
		if (visited[node])
			continue;	// 탐색이 완료된 노드

		// 탐색을 시작하기 전 같은 그룹인지 식별하는 자료구조를 추가한다.
		map<int, int> group;
		group.insert({ node, 0 });

		visited[node] = true;
		int groupMemberCnt = 1;

		int noneGroupMember = DFS_checkCycle(node, visited, /*groupVisited*/group, groupMemberCnt, Want);

		cnt += noneGroupMember;
	}

	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> T;
	vector<int> answers(T);

	for (int t = 0; t < T; t++) {
		cin >> N;
		vector<int> Want(N + 1);
		for (int i = 1; i <= N; i++) {
			int want;
			cin >> want;
			Want[i] = want;
		}

		answers[t] = solution(Want);
	}

	for (int i = 0; i < T; i++) {
		cout << answers[i] << '\n';
	}
}