알고리즘(C++) / 백준 9466 : 텀 프로젝트

9466

boj.kr/9466

9466번: 텀 프로젝트

 

문제

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

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

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

1234567

1	2	3	4	5	6	7
3	1	3	7	3	4	6

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

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

 

입력

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

 

출력

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

 

코드

//9466 텀 프로젝트
#include <iostream>
#include <cstring>
using namespace std;
int visited[100001] = { 0, };
int student[100001] = { 0, };
bool check[100001] = { false, };

void DFS(int node) {
	visited[node]++;

	int next = student[node];
	if (check[next] == true) {
		check[node] = true;
		return;
	}

	if (visited[node] > 2) {
		return;
	}

	DFS(next);
	check[node] = true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	
	int n;
	int s;

	for (int i = 0; i < T; i++) {
		memset(student, 0, sizeof(student));
		memset(visited, 0, sizeof(visited));
		memset(check, 0, sizeof(check));

		cin >> n;

		for (int j = 1; j <= n; j++) {
			cin >> s;
			student[j] = s;
		}
		for (int j = 1; j <= n; j++) {
			if (visited[j] == 0)
				DFS(j);
		}

		int num = 0;
		for (int j = 1; j <= n; j++) {
			if (visited[j] == 1) {
				num++;
			}
		}
		cout << num << "\n";
	}

	return 0;
}

 

설명

그림으로 설명한다. 

 

student 배열은 함께하고 싶은 학생이 저장되어있는 배열

visited 배열은 몇번 방문되었는지 저장되어있는 배열

check 배열은 방문되었는지 확인하는 배열

 

사이클이라는 것을 판단하기 위해서는 2번 이상 방문을 해야한다. 

다음과 같은 그림이 있을때 1번부터 시작하면 1, 3, 4, 5, 3, 4, 5를 차례대로 방문한다. 사이클이라는 것을 판단하기 위해서 사이클에 포함되어 있는 노드들은 두번 이상 방문한다. 사이클이 시작하는 3번 노드가 방문 횟수가 세번이 되면 함수가 종료한다. 

check 배열로 방문이 되었는지 확인하고 방문되었다면 함수가 종료된다. 

 

출력은 방문이 한 번만 된 노드들의 개수를 출력한다. 

 

결과

 

고찰

생각보다 문제가 까다로웠다. 단순하게 사이클만 찾으면 될거라고 생각했지만 단순하지 않았다.

신경쓸게 꽤 있었던 문제였다. 

방문한 횟수 visited와 방문여부 check 배열을 나눠서 구현하는 것이 중요헀다. 

 

난이도

●●○○○