백준 9466번 - 텀 프로젝트 (C++)

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

9466번: 텀 프로젝트

 

위 문제를 보고 그래프 문제라는 것을 깨닫는 것이 첫번째 단계다.

문제에서 주어진 예제

 

여기서 1~7을 노드라고 생각하자. 그리고 아래 숫자들은 노드가 가리키는 또다른 노드라고 생각하면, 위 표는 아래같은 그래프로 나타낼 수 있다.

 

3 -> 3 은 표현이 안됐는데, 있다고 생각해줘라

 

이제 이 문제가 파악이 될 것이다. 이 문제는 그래프로 나타낸 뒤 사이클을 파악하는 것이 핵심이다. 

이제 이것을 어떻게 파악해야할까.

 

가장 쉬운 것은 모든 노드에서 dfs를 돌리면서 자기 자신으로 돌아오는지 확인하는 것이 가장 쉽다. 그러나 이 방법의 시간복잡도는 O(N * N)으로 TLE 판정을 피할 수 없다.

 

DFS의 특성을 잘 생각해보자. DFS는 갈 수 있는 곳을 끝까지 파고들었다가 돌아온다. 즉, 끝까지 파고들었는데도 나 자신으로 돌아오지 않았다면 이 시작 노드는 사이클에 포함되지 않는다는 의미이다. 그리고 더 나아가 이 노드에서 시작해서 도달하는 다른 노드들도 DFS의 특성상 다시 시작으로 들어가지 않아도된다.

그러므로 2에서 시작해서 3까지 도달했으니까 1, 3은 시작으로 치지 않아도 된다.

 

이렇게되면 모든 노드에 1번만 도달하기 때문에 탐색만 따질 때 O(N)이된다.

 

그렇다면 이제 가장 중요한 사이클 판단이다.

 

void dfs(int NowNode) {
	visited[NowNode] = true;

	int nextNode = node[NowNode];

	if (visited[nextNode] == false) {
		visited[nextNode] = true;
		dfs(nextNode);
	}
	else if (!CycleCheck[nextNode]) { // 사이클 발견
		//cout << NowNode << endl;
		Cycle(NowNode);
	}

	CycleCheck[NowNode] = true;

	return;
}

 

방향 그래프에서 사이클 확인은 dfs에서 만약 방문했던 노드를 다시 방문했다면 이것은 사이클을 만났다고 할 수 있다. 

그리고 사이클에 포함된 노드들에 체크를 해준다. 그리고 이후 체크가 안된 노드의 수가 정답이된다. 중요한 건 사이클을 발견했을 때다.

그리고 여기서 중요한 건 다음 visited가 true라고 전부 판단해버리면 사이클이 아니라 그저 서로 다른 노드가 두번 방문한 것인데도 사이클로 판단해버릴 수 있기 때문에 방문했고, 첫 사이클 발견일 때 사이클을 체크해준다.

 

 

#include <iostream>
#include <vector>
using namespace std;

int node[100001];
bool CycleCheck[100001];
bool visited[100001];
bool CycleNumber[100001];

int N;
int answer = 0;
void init() {
	for (int i = 1; i < 100001; i++) {
		node[i] = 0;
		CycleCheck[i] = false;
		visited[i] = false;
		CycleNumber[i] = false;
	}
	answer = 0;
}

void Cycle(int Node) {
	if (CycleNumber[Node]) return;
	
	CycleNumber[Node] = true;
	Cycle(node[Node]);
}

void dfs(int NowNode) {
	visited[NowNode] = true;

	int nextNode = node[NowNode];

	if (visited[nextNode] == false) {
		visited[nextNode] = true;
		dfs(nextNode);
	}
	else if (!CycleCheck[nextNode]) { // 사이클 발견
		//cout << NowNode << endl;
		Cycle(NowNode);
	}

	CycleCheck[NowNode] = true;

	return;
}

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

	int T;
	cin >> T;

	for (int t = 0; t < T; t++) {
		init();

		cin >> N;
	
		for (int i = 1; i <= N; i++) {
			cin >> node[i];
		}

		for (int i = 1; i <= N; i++) {
			if (CycleCheck[i]) continue;
			dfs(i);

			for (int j = 1; j <= N; j++) visited[i] = false;
		}
		
		for (int i = 1; i <= N; i++) {
			if (!CycleNumber[i]) answer++;
		}

		cout << answer << '\n';
	}
}