백준 9466 텀 프로젝트 c++ (dfs)

문제 출처 : https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1234567

3

1

3

7

3

4

6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

풀이

우선 문제는 학생들의 팀을 구성하는 문제로, 사이클이 존재한다면 해당 사이클의 학생들은 같은 팀이 된다.

계속된 시간 초과로 더 이상의 최적화 방법을 떠올리지 못해, 아래의 블로그를 참고하였다.

https://jaimemin.tistory.com/674

해당 블로그 풀이와 내 풀이는 비슷한 듯 달랐다.

본인은 모든 학생에 대해 dfs를 했으며 사이클이 완성된 학생은 dfs를 하지 않았다.

이 풀이는 모든 학생을 dfs 하는 N번의 반복문안에 사이클을 찾는 최대 N번의 반복문이 포함되어

O(N^2)의 시간 복잡도로 아무리 최적화해도 82퍼에서 시간 초과가 떴다.

블로그를 참고한 풀이는 방문하지 않은 학생만 dfs를 했다.

만약 1번 학생을 dfs했을 때, 3번 학생과 5번 학생을 방문했다면, 3번 학생과 5번 학생은 dfs를 하지 않는 풀이이다.

이 풀이는 모든 학생에 대해 한 번씩만 방문하므로 O(N)의 시간 복잡도로 풀 수 있다.

코드(통과)

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 100001
using namespace std;

int t, n;
int graph[MAX];
bool visited[MAX];
bool done[MAX];
int cnt;
void hasCycle( int node) {

	visited[node] = true;
	int next = graph[node];

	
	if (!visited[next]) {
		hasCycle( next);
	}
	else if (!done[next]) {//방문은 했지만 아직 사이클이 아니라면 next까지 포함해서 사이클 완성
		//자기 자신을 포함한 팀의 멤버를 카운트
		for (int i = next; i != node; i = graph[i]) {
			cnt++;
		}
		cnt++;
	}
	done[node] = true;
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> graph[i];
		}
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				hasCycle(i);
			}
		}
		cout << n-cnt << '\n';
		cnt = 0;
		memset(visited, false, sizeof(visited));
		memset(done, false, sizeof(done));
	}


	return 0;
}

코드(시간 초과)

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 100001
using namespace std;

int t, n;
int graph[MAX];
bool visited[MAX];
bool cycle[MAX];
bool isCycle;
void hasCycle(int firstnode, int node) {

	visited[node] = true;
	int next = graph[node];

	if (!visited[next] && !cycle[next])
		hasCycle(firstnode, next);
	else {
        //사이클이 완성된 경우
		if (next == firstnode) {
			isCycle = true;
		}
        //본인이 본인을 가리키는 경우
		if (node == next) {
			cycle[node] = true;
		}
	}
	if (isCycle)
		cycle[node] = true;
	visited[node] = false;
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n;
		int result = 0;
		for (int i = 1; i <= n; i++) {
			cin >> graph[i];
		}
		for (int i = 1; i <= n; i++) {
            //사이클이 존재하면 이미 그룹이 되어있기 때문에 탐색 x
			if (!cycle[i]) {
				if (graph[i] < i && !cycle[graph[i]])
					continue;
				hasCycle(i, i);
				isCycle = false;
			}
		}
		for (int i = 1; i <= n; i++) {
			if (!cycle[i])
				result++;
		}
		cout << result << '\n';
		memset(cycle, false, sizeof(cycle));
	}


	return 0;
}