백준:9466번 팀 프로젝트

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

9466번: 텀 프로젝트

이번 문제를 풀때 생각했던 것은 사이클과 DFS 이다. 일단 사이클은 이미 방문한 지점을 다시 들르면 사이클이라 정의했었다. 

나는 접근을 맨 처음 들어간 값과 마지막이 가리키는 값이 일치하면 사이클로 1개씩 추가하고 배열들을 매번 초기화 해줬다. 밑에 코드를 보자

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<cstring>
#include<stack>
#include<queue>
#define PI 3.1415926535
using namespace std;
bool check1[100001] = { 0 };
bool check2[1001] = { 0 };
vector<int> d[100001];

int cnt = 0;
void dfstack(int start,int p) {                       //스택을 이용한 dfs
	memset(check1, false, (p + 1) * sizeof(bool));
	stack<int> s;
	int current = start;
	s.push(current);
	check1[current] = true;
	while (!s.empty()) {
		current = s.top();
		s.pop();
		int temp = d[current].size();
		for (int i = 0; i < temp; i++) {
			int next = d[current][i];
			if (next == start)                  //첫 시작과 같으면 사이클로 인정
				cycle = true;
			if (check1[next] == false) {
				check1[next] = true;
				s.push(current);
				s.push(next);
				break;
			}
		}
	}
}
int main()
{
	int n, p,t;
	vector<int> a;
	cin >> t;
	while (t--) {
		int cnt = 0;
		cin >> n;
		a.clear();
		a.push_back(0);
		for (int i = 1; i <= n; i++) {
			cin >> p;
			a.push_back(p);
		}
		for (int i = 1; i <= n; i++) {
			d[i].clear();                    /계속 초기화
			d[i].push_back(a[i]);
		}
		for (int i = 1; i <= n; i++) {
			dfstack(i,n);
			if (cycle == false)           //사이클이 아니면 값추가
				cnt++;
			cycle = false;
		}
		cout << cnt << '\n';        //정답
	}
	


	return 0;
}

이 코드를 보면 답은 일치하게 나온다. 그렇지만 배열을 반복문을 돌릴때마다 초기화를 하기 때문에 시간초과가 걸린다.

결국 이 방법은 효율적이지 못한다. 이렇게  매번 초기화하면서 값을 추가한 이유는 사이클이 겹치면서 구분지어줄 방법이 없었기 때문이다. 

그래서 사이클이 만들어질때 시작한 값을 미리 지정을 하면 사이클내에서도 중복된 것을 뺼 수있다. 

밑에 코드를 보자

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<cstring>
#include<stack>
using namespace std;
int check1[100001] = { 0 };
bool check2[1001] = { 0 };
vector<int> d[100001];
int cnt = 0;
int s[100001] = { 0 };
int ans = 0;
int dfs(int a, int cnt, int start) {
	if (check1[a] != 0) {                 //이미 방문 되어있고
		if (start != s[a]) {               //시작했던 값이 다르면 즉 이미 1번으로 3번을 방문했었다면 두번 방문 방지
			return 0;
		}
		return cnt - check1[a];            //아니면 사이클까지 걸린 방문수에서 사이클 시작한 방문수 뻄
	}
	check1[a] = cnt;                             //몇번째 방문인지 값 넣기
	s[a] = start;                                //몇번 정점으로 시작했는지
	for (int i = 0; i < d[a].size(); i++) {
		int next = d[a][i];
		if (check1[i] == 0)
			return dfs(next, cnt + 1, start);
	}
}
int main()
{
	int n, p,t;
	vector<int> a;
	cin >> t;
	
	while (t--) {
		int cnt = 0;
		cin >> n;
		a.clear();
		a.push_back(0);
		for (int i = 1; i <= n; i++) {
			cin >> p;
			a.push_back(p);
		}
		for (int i = 1; i <= n; i++) {
			d[i].clear();
			d[i].push_back(a[i]);
			s[i] = 0;
			check1[i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			if(check1[i]==0)
				ans+=dfs(i,1,i);
		}
		cout << n-ans << '\n';
		ans = 0;
	}
	


	return 0;
}

이 코드를 보면 굳이 배열을 초기화를 굳이 안해도 이미 세어버린 사이클은 시작정점으로 구분지으면서 중복안되게 한다.