BOJ 9466 : 텀 프로젝트

BOJ 9466 : 텀 프로젝트

[BOJ 9466 (G4) 리뷰]

 

처음엔 간단해보였지만 풀다보니 생각하지 못한 경우의 수 때문에 애를 많이 먹었다.

처음엔 단순히 싸이클이 존재할때만 해당 학생들을 제외하여 코딩을 했는데 틀렸다고 나왔고 반례를 찾아보니

1->3->5->3과 같이 중간부터 싸이클이 시작될 경우를 고려하지 않았다.

다시 머리를 싸맨 후 싸이클이 도는 학생들만 제외를 시키도록 하였고 제출을 했으나 시간초과가 나왔다....

코드 중간에 싸이클에 속하지않은 학생들을 걸러내는 작업에서 O(n^2)가 되었던것 같다.

포기할까 했지만 억지스러운 최적화 후에 정답처리가 되었다. 효율적인 코드인지는 모르겠다 ..

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

int student[100002];
int check[100002];
int n;
int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(0);
	int tc;
	cin >> tc;
	while (tc--)
	{
		cin >> n;
		fill(student, student + n + 1, 0);
		fill(check, check + n + 1, 0);

		for (int i = 1; i <= n; i++)
		{
			cin >> student[i];
			if (student[i] == i) //자기 자신을 지목한사람 제외
				check[i] = -1; //방문할 필요 없으므로 방문처리
		}


		for (int i = 1; i <= n; i++) //1번부터 n번까지 학생에대해 확인을 한다.
		{
			if (check[i] != 0) continue;
			queue <int> Q;
			Q.push(i);
			check[i] = i;
			int nxt = 0;
			int cur = 0;
			while (!Q.empty())
			{
				cur = Q.front();		
				Q.pop();
				nxt = student[cur];
				if (check[nxt] == i)
				{
					check[cur] = -1;
					while (1)
					{
						if (nxt == cur) break;
						check[nxt] = -1;
						nxt = student[nxt];
					}
				}
				if (nxt < 1 || nxt >n) continue;
				if (check[nxt] != 0) continue;
				check[nxt] = i;
				Q.push(nxt);
			}
			int cycle = i;
			while (cycle!=nxt)
			{
				if (check[cycle] == i)
				{
					check[i] = 0;
				}
				cycle = student[cycle];
			}
		}

		int sum = 0;
		for (int i = 1; i <= n; i++)
		{
			if (check[i] != -1)
			{
				sum += 1;
			}
		}

		cout << sum<<'\n';

	}

}