백준 9466 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

기본적인 정해는 사이클을 찾아서 각 사이클이 돈다면 그룹으로 나눠주고, 돌지 않는다면  카운팅 해주는 식이다.

그러나 낮은 정답률에서 보면 알 수 있듯 생각 없이 대충 풀다 보면 O(N^2) 풀이로는 시간 초과가 나게 된다.

 

1, 2, 3, 4, 5, , , , , , , 99999, 100000 이런식으로 나온다면 1부터 10만까지 2부터 10만까지,, 쭉 돌다 보면 TLE이다.

 

나 또한 시간초과에서 벗어날 수 없어서 다른 사람의 풀이를 참고하던 중 참신한 풀이를 발견했다.

 

#include <cstdio>
#include <queue>
using namespace std;

int ar[100001], cnt[100001], ans;
queue<int> Q;

void Solved() {
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		ans++;
		cnt[ar[cur]]--;
		if (cnt[ar[cur]] == 0) Q.push(ar[cur]);
	}
}

int main() {
	int tc, n;
	scanf("%d", &tc);
	while (tc--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &ar[i]);
			cnt[ar[i]]++;
		}

		for (int i = 1; i <= n; i++) 
			if (cnt[i] == 0) Q.push(i); 
		
		Solved();
		printf("%d\n", ans);
		ans = 0;
		fill(cnt, cnt + n, 0);
	}
	return 0;
}

기본적인 풀이는 다음과 같다.

 

1. 각 배열을 입력받고 그 수가 최대 10만을 넘지 않으니 cnt함수에 ar[i]를 인덱스로 해서 넣어준다.

 

2. cnt[i]가 0이라면 한 번도 호출되지 않은 배열이니 큐에 넣어준다.

 

3. 큐의 front를 빼서 ar에 넣어주고 호출 횟수를 1 줄인다.

 

4. 만약 호출 횟수를 1뺏는데 0이라면 다시 큐에 그 인덱스를 큐에 넣어준다.

 

이런 식으로 큐가 빌때까지 반복해주고 출력한다.