🙇‍♀️[Gold III] 텀 프로젝트 - 9466

문제 링크

성능 요약

메모리: 7116 KB, 시간: 536 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 3월 11일 20:31:07

문제 설명

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

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

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

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까지 번호가 부여된다.)

출력

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

🚀풀이

시간초과로 결국 다른 사람의 코드를 참조했다.ㅠㅠ

시간 초과 났던 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// 사이클을 어떻게 판별하지

int t, n;
vector<int> graph;
void solve()
{
	cin >> t;
	for (int i = 1; i <= t; ++i)
	{
		cin >> n;
		graph.clear();
		graph.resize(n + 1);
		int wanted;
		for (int j = 1; j <= n; ++j)
		{
			cin >> wanted;
			graph[j] = wanted;
		}

		int cnt = n;
		//vector<bool> ch(n + 1);
		vector<bool> ch2(n + 1);

		for (int j = 1; j <= n; ++j)
		{
			int value = graph[j];
			// 자기 자신을 팀으로 정할 때
			if (value == j)
			{
				cnt--;
				//ch2[j] = true;
				continue;
			}
			if (ch2[j] == true)
				continue;

			vector<bool> ch(n + 1);
			ch[j] = true;
			ch[value] = true;
			int temp = 2;

			// 사이클일 수 있으니 기록하기
			vector<int> cache;
			cache.push_back(j);
			cache.push_back(value);

			while (true)
			{
				if (ch[graph[value]] == true)
				{
					// 사이클임
					if (graph[value] == j)
					{
						cnt -= temp;

						for (int k = 0; k < cache.size(); ++k)
						{
							ch2[cache[k]] = true;
						}
					}
					break;
				}
				ch[graph[value]] = true;
				cache.push_back(graph[value]);
				value = graph[value];
				temp++;
			}

			//ch.clear();
			//ch.resize(n + 1);
		}

		cout << cnt << '\n';
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

80퍼에서 계속 시간초과가 나서 결국 포기함..

다른 사람 코드를 보니 사이클 판별을 dfs로 풀었다.

void isCycle(int here)
{
    // 방문하기
	visited[here] = true;
	int next = graph[here];

    // 다음거 방문안했으면 재귀
	if (visited[next] == false)
		isCycle(next);
	else if (done[next] == false)
	{
        // 방문은 했지만 사이클이 아니라면 next까지 포함해서 사이클 완성하기
        // 자기 자신을 포함한 팀의 수를 센다.
		for (int i = next; i != here; i = graph[i])
			cnt++;
		cnt++;
	}

    // 사이클 완성됐다.
	done[here] = true;
}

void solve()
{
	cin >> t;
	for (int i = 1; i <= t; ++i)
	{
		cin >> n;
		graph.clear();
		graph.resize(n + 1);
		visited.clear();
		visited.resize(MAX);
		done.clear();
		done.resize(MAX);
		for (int j = 1; j <= n; ++j)
		{
			cin >> graph[j];
		}
		for (int i = 1; i <= n; ++i)
		{
			if (visited[i] == false)
				isCycle(i);
		}

		cout << n - cnt << '\n';
		cnt = 0;
		visited.clear();
		visited.resize(MAX);
		done.clear();
		done.resize(MAX);
	}
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

const int MAX = 100001;
int t, n, cnt;
vector<int> graph;
vector<bool> visited;
vector<bool> done;

void isCycle(int here)
{
	visited[here] = true;
	int next = graph[here];

	if (visited[next] == false)
		isCycle(next);
	else if (done[next] == false)
	{
		for (int i = next; i != here; i = graph[i])
			cnt++;
		cnt++;
	}

	done[here] = true;
}

void solve()
{
	cin >> t;
	for (int i = 1; i <= t; ++i)
	{
		cin >> n;
		graph.clear();
		graph.resize(n + 1);
		visited.clear();
		visited.resize(MAX);
		done.clear();
		done.resize(MAX);
		for (int j = 1; j <= n; ++j)
		{
			cin >> graph[j];
		}
		for (int i = 1; i <= n; ++i)
		{
			if (visited[i] == false)
				isCycle(i);
		}

		cout << n - cnt << '\n';
		cnt = 0;
		visited.clear();
		visited.resize(MAX);
		done.clear();
		done.resize(MAX);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고