BOJ 2668 - 숫자고르기

문제

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

풀이

주어진 배열에서 순환하는 요소가 총 몇개인지 카운팅하고, 순환하는 요소들을 오름차순으로 출력하는 문제이다. 아래의 예제 이미지를 보면 순환하는 요소는 1-3, 5 이렇게 3개이다.

정점 N에서 시작하는 순환 배열이 존재하는가를 확인하려면 도착점을 N으로 두고 MAP[N]부터 시작해서 마지막에 N으로 오는가를 확인하면 된다. 만약 N으로 오지 않고 이미 방문했던 정점을 다시 방문한다면 순환 배열이 존재하지 않는다는 뜻이다.

나는 따로 방문을 표시할 배열과 사이클 여부를 표시할 배열을 따로 만들지 않고 방문을 표시할 배열의 값을 0, 1, 2로 구분지어 방문하지 않음, 방문함, 이미 방문했고 사이클이다 라고 정의하여 O(2N)의 공간을 사용하였다.

#include <stdio.h>
int n,map[101]={0},visit[101]={0};
int isCircular(int start, int cur, int count){
	if(visit[cur]) return 0;
	visit[cur] = 1;
	if(start == cur) {
		
		int i;
		for(i=1;i<=n;i++){
			if(visit[i] == 1) visit[i]=2;
		}
		return count+1;
	}
	return isCircular(start,map[cur],count+1);
}
int main(){
	int i,j,ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&map[i]);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(visit[j]==1) visit[j]=0;
		}
		ans += isCircular(i,map[i],0);
	}
	printf("%d\n",ans);
	for(i=1;i<=n;i++){
		if(visit[i]==2)
			printf("%d\n", i);
	}
}