[백준] 9466번 텀 프로젝트 [C++]

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

9466번: 텀 프로젝트

---

---

접근 방식

문제를 읽고, 해당 표에 대해서 그림을 그려보면

이러한 형태가 된다.

이 때, 프로젝트가 가능한 팀은 (3) , (4 ,6, 7) 이다. 따라서 이 문제의 답은 (1,2,5) 3개다.

즉 그림으로 보면 더 이해가 잘 되지만, 싸이클을 이루지 않는 원소의 수가 문제의 답이 된다는 뜻이다.

따라서, 이 문제를 해결하기 위해서 1번부터 n번까지 , 각각이 선택한 원소를 모두 탐색을 해 싸이클을 이루는지 확인만 해주면 된다.

이 확인은 예를 들어 1번 노드로부터 탐색을 시작하면 탐색을 계속해 만나게 된 모든 노드에 1번이라는 숫자를 부여해준다.

계속해서 탐색을 하는데, 배열에 1번이라는 숫자가 있는 노드를 다시 만나게 된다면 이는 이미 들른 곳에 한번 더 오게 된 것이기 때문에 이는 싸이클에 포함이 된다는 얘기다. 따라서 이 노드들을 체크해준다.

계속해서 탐색을 하는데, 이미 체크가 된 노드를 만나면 싸이클을 한번 더 도는 것이기 때문에 더 탐색할 필요가 없다.

이 경우는 탐색을 종료해준다.

이미 탐색을 한번이라도 한 노드(배열에 초깃값이 아닌 다른 숫자가 있는 경우)는 더 탐색할 필요가 없다. 이미 싸이클에 포함이 되면 체크가 되었을거고, 아니더라도 더 탐색을 할 이유가 없다.

 

 

---

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<tuple>
#include<string>
using namespace std;
int arr[100001];
int t, n;
int par[100001];
bool flag[100001];
vector<int> v;
void dfs(int n,int s) {
	if (flag[n])return; //이미 체크가 되었을 경우에는 종료해준다.
	if (par[n] ==s) { //초기 노드와 배열의 번호가 같다면 싸이클에 포함이 되었기 때문
		flag[n] = true;
	}
	else
	par[n] = s; 
	dfs(arr[n],s);
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> t;
	for (int a = 0; a < t; a++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			par[i] = 0;
			flag[i] = false;
		}
		int counter = 0;
		for (int i = 1; i <= n; i++) {
			if(par[i]==0) //처음으로 탐색 될 경우
			dfs(i, i);
			if (!flag[i])counter++;
			flag[i] = true; //이미 싸이클인지 아닌지 체크한 노드는 더 탐색을 안해도 되기 때문
		}
		cout << counter << '\n';

	}
}

---

 

O(n)으로 구현했다 생각했는데, 탐색이 여러번 되는 경우를 생각을 못 해서 시간 초과로 꽤 고생한 문제였다.