9466번: 텀 프로젝트 (BOJ C/C++)

9466번: 텀 프로젝트

사용 언어: C++

 

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1234567

3

1

3

7

3

4

6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

풀이

문제를 읽고 생각을 해보면 시작하는 곳에서 돌아오는 곳인 사이클을 만들어야하고 사이클이 형성되지 않으면 따로 체크를 해야하고 사이클이 형성이 되면 형성이 되는 부류끼리 사이클이 형성이 된다고 체크를 해야한다. 그래서 풀어보다가 모르겠어서 바킹독님의 풀이 해설을 보았습니다.

%바킹독님의 풀이를 전면적으로 분석해서 올린 풀이입니다.%

 

x에서 시작했다고 가정했을때

 

1.1. 사이클에 포함된 학생 or 포함 X 학생 재방문 -> x는 사이클 포함 X
2.1. x가 아닌 다른 학생 y를 재방문하면 x는 사이클 X, y는 사이클 O.
-> y에서 출발해서 다시 y까지 만나는 학생들 사이클 포함 학생
-> x에서 y까지 가는 도중 학생들은 사이클 X
2.2. x가 x 재방문하면 x는 사이클 O. 그리고 x에서 출발해 다시 x까지
만나는 학생들도 사이클 O.
 각 학생을 최대 2번 방문 -> O(N)

 

 -> 이것을 줄여서
 1. 이번 방문에서 지나간 학생에 도달했을 경우 -> 지나간 학생까지 학생들 사이클 포함 O
 2. 이전 방문에서 지나간 학생에 도달했을 경우 -> 도달하기까지 학생들은 사이클 포함 X

#include <bits/stdc++.h>
using namespace std;

int arr[100005];
int state[100005];
int n;

const int NOT_VISITED = 0;
const int CYCLE_IN = -1;

void run(int x)
{
	int cur = x;
	while(true)
	{
		state[cur] = x;
		cur = arr[cur];
		//이번 방문에서 지나간 학생에 도달했을 경우
		if(state[cur] == x)
		{
			while(state[cur] != CYCLE_IN) //사이클 안에 있는 학생들 전부 체크
			{
				state[cur] = CYCLE_IN;
				cur = arr[cur];
			}
			return;
		}
		//이전 방문에서 지나간 학생에 도달했을 경우
		else if(state[cur] != 0) return; //이미 visited 상태라면(조건 1.1번) 그냥 넘기기
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--)
	{
		cin >> n;
		fill(state+1, state+n+1, 0);
		for(int i=1; i<=n; i++)
			cin>>arr[i];
		int ans=0;
		for(int i=1; i<=n; i++)
		{
			if(state[i] == NOT_VISITED)
				run(i);
		}
		int cnt=0;
		for(int i=1; i<=n; i++)
		{
			if(state[i] != CYCLE_IN)
				cnt++;
		}
		cout<<cnt<<'\n';
	}
	
	return 0;
}

또한 바킹독님이 O(N^2) 풀이도 알려주셨다.

 

시간 초과 풀이

#include <bits/stdc++.h>
using namespace std;

int arr[100005];
int n;

bool iscycle(int idx)
{
	int cur = idx;
	for(int i=0; i<n; i++)
	{
		cur = arr[cur];
		if(cur == idx) return true;
	}
	return false;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		cin>>n;
		for(int i=1; i<=n; i++)
			cin>>arr[i];
		int ans = 0 ;
		for(int i=1; i<=n; i++)
			if(!iscycle(i)) 
				ans++;
		cout<<ans<<'\n';
	}
	
	return 0;
}

이렇게 하면 시간 초과가 뜰텐데 이유는 visited를 매번 초기화하거나 새로 만들어야하면 O(N^2)이나 그 이상이 되서 그렇다. 그래서 첫 풀이와 같이 visited 여부 확인하는 값을 매번 다르게 넣어서 O(N)으로 만들 수 있다.