백준 9466 c++ "텀 프로젝트" -PlusUltraCode-

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

[필자 사고]

재미난 문제다.

dfs탐색을 이용해야 되는 문제인데 이 문제만의 핵심 포인트는 순환을 어떻게 처리할지에 관한것이다.

만약 dfs탐색도중 이미 방문한 곳이 다음 곳이라면 성공!! 순환이 발생한 것이다.

이럴 경우 for문을 이용해 다시 원위치로 될때가지 반복문을 돌린다.

 

그 다음 마지막에 완전 탐색 완료 표시인 visited[now] = 2를 통해 탐색을 종료한다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

이 문제는 학생들이 한 명씩 “함께 프로젝트를 하고 싶은 학생”을 선택했을 때, 그 결과로 만들어지는 연결 관계 속에서 사이클(순환) 을 이루는 학생들만이 팀을 구성할 수 있다는 점을 이용한다. 즉, 사이클에 포함되지 않은 학생은 어떤 팀에도 속하지 못한다.

핵심 아이디어는 단방향 그래프에서 사이클을 찾는 것이다.
각 학생은 한 명만 선택하므로 모든 노드는 출차 간선이 1개인 그래프 형태가 된다. 따라서 DFS(깊이 우선 탐색)를 이용하면 효율적으로 사이클을 찾을 수 있다.

탐색 과정에서는 방문 상태를 세 가지로 나눈다.
0은 아직 방문하지 않은 상태, 1은 현재 탐색 중인 상태, 2는 탐색이 완료된 상태를 의미한다.
DFS를 돌며 아직 방문하지 않은 노드를 재귀적으로 탐색하다가, 이미 방문 중(1)인 노드를 다시 만나면 그 구간이 사이클임을 알 수 있다. 이때 해당 구간에 포함된 학생 수를 카운트하여 팀 인원 수를 구한다.
탐색이 끝난 노드는 2로 표시해, 중복 탐색을 방지하고 시간 복잡도를 줄인다.

모든 노드에 대해 DFS를 수행한 뒤, 전체 학생 수에서 사이클에 포함된 학생 수를 빼면 팀에 속하지 못한 학생 수를 얻을 수 있다.
이 방법은 각 노드가 한 번씩만 방문되므로 시간 복잡도는 O(N)이며, N이 최대 100,000일 때도 충분히 효율적으로 동작한다.

결과적으로 이 알고리즘은 다음 과정을 따른다.

1. 학생의 선택 관계를 그래프로 저장한다.
2. DFS로 각 학생의 연결 경로를 탐색한다.
3. 탐색 중 자기 자신으로 돌아오면 사이클(팀)을 발견한 것이다.
4. 팀에 속한 학생 수를 카운트하고, 전체 학생 수에서 제외한다.
5. 팀에 속하지 못한 학생 수를 출력한다.

이 과정을 통해 문제에서 요구하는 “어느 팀에도 속하지 못한 학생의 수”를 정확히 계산할 수 있다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> visited;
vector<int> graph;
int cnt = 0;

void dfs(int now) {
	visited[now] = 1;
	int next = graph[now];

	if (!visited[next])dfs(next);
	else if (visited[next] == 1) {
		for (int i = next; i != now; i = graph[i]) {
			cnt++;
		}
		cnt++;
	}


	visited[now] = 2;
}

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

	int T;
	cin >> T;
	while (T--) {
		cin >> N;
		visited.assign(N + 1, 0);
		graph.assign(N + 1, 0);
		cnt = 0;

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

		for (int i = 1; i <= N; i++) {
			if (!visited[i])dfs(i);
		}
		cout << N - cnt << '\n';

	}
}