[ C++ 백준 9466 ] 텀 프로젝트

문제_링크

9466번: 텀 프로젝트

---

 

---

자세한 설명은 생략한다.

( 설명과 관련해서는 다른 사람이 더 잘해둔 게 많아서 내가 참고한 블로그 링크를 아래에 적어두겠다. )

참고_링크

---

 

일단 80%에서 시간 초과가 난 코드이다.

시간 복잡도를 O(N)으로 짠 것 같다고 생각했는데 문제가 발생했다.

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int students[100002];
bool visited[100002];
int checkNum[100002]; // -1이면 미그룹, 0이면 미방문, 1이면 그룹

//80% 시간 초과
void DFS(int n)
{
	if (checkNum[n] != 0)
		return;

	if (visited[n] == true)
	{
		checkNum[n] = 1;
		int numLoop = students[n];
		while (numLoop != n && !checkNum[numLoop])
		{
			checkNum[numLoop] = 1;
			numLoop = students[numLoop];
		}
		return;
	}

	visited[n] = true;
	DFS(students[n]);
}

void NonCheckDFS(int n)
{
	if (checkNum[n] == 1)
		return;

	checkNum[n] = -1;
	NonCheckDFS(students[n]);
}

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

	int repeat, studentNum;

	cin >> repeat;
	for (int i = 0; i < repeat; ++i)
	{
		cin >> studentNum;
		fill(visited, visited + studentNum + 1, false);
		fill(checkNum, checkNum + studentNum + 1, 0);

		for (int idx = 1; idx <= studentNum; ++idx)
		{
			cin >> students[idx];
		}

		for (int n = 1; n <= studentNum; ++n)
		{
			if (visited[n] == true)
				continue;
			
			DFS(n);		
			NonCheckDFS(n);
		}

		int ansCnt = 0;
		for (int n = 1; n <= studentNum; ++n)
		{
			if (checkNum[n] == -1)
				ansCnt++;
		}
		cout << ansCnt << '\n';
	}
}

 

아무래도 NonCheckDFS로 한 번 더 체크하는 것과 visited배열이 문제인 거 같다고 생각해서, 코드를 살짝 수정했다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int students[100002];
int checkNum[100002]; // -1이면 미그룹, 0이면 미방문, 1이면 그룹, 2면 방문

//80% 시간 초과
void DFS(int n)
{
	int startNum = n;
	while (true)
	{
		if (checkNum[n] == -1 || checkNum[n] == 1)
			break;

		if (checkNum[n] == 2) // 사이클 체크
		{
			checkNum[n] = 1;
			int numLoop = students[n];
			while (numLoop != n && !checkNum[numLoop])
			{
				checkNum[numLoop] = 1;
				numLoop = students[numLoop];
			}
			break;
		}

		checkNum[n] = 2;

		n = students[n];
	}

	// 미그룹 체크
	n = startNum;
	while (checkNum[n] == 2)
	{
		checkNum[n] = -1;
		n = students[n];
	}
}

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

	int repeat, studentNum;

	cin >> repeat;
	for (int i = 0; i < repeat; ++i)
	{
		cin >> studentNum;
		fill(checkNum, checkNum + studentNum + 1, 0);	// 이놈들?

		for (int idx = 1; idx <= studentNum; ++idx)
		{
			cin >> students[idx];
		}

		for (int n = 1; n <= studentNum; ++n)
		{
			if (checkNum[n] != 0)
				continue;
			
			DFS(n);			//
		}

		int ansCnt = 0;
		for (int n = 1; n <= studentNum; ++n)
		{
			if (checkNum[n] == -1)
				ansCnt++;
		}
		cout << ansCnt << '\n';
	}
}

 

그렇게 해서 해결한 코드다.

 

---

문제 푼 시간: 3시간

느낀 점:

쉬울 것 같아서 시도했는데 생각보다 어려웠다.

시간 복잡도 관련 개념을 다시 한 번 잡아두는 게 좋을 것 같다.