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

 

9466번: 텀 프로젝트

그래프에서 사이클을 찾고 사이클을 이루지 않는 노드들의 갯수를 세는 문제다.
제한시간에 걸리지 않기 위해서는 탐색했던 노드를 다시 방문하지 않도록 해야 한다.

 

 

 

학생들이 노드로 주어지며 다른 학생을 지목하는 간선을 통해서 그래프(Graph)가 만들어진다.

그래프에서 사이클(Cycle) 은 특정 노드에서 탐색해가다가 다시 해당 노드로 돌아오게되는 형태의 연결을 말한다.

팀은 자기 자신을 지목한 학생이나 사이클을 이루는 학생들로 만들어지며 팀을 이루지 못한 학생들의 수를 카운트 하면 된다.

 

 

문제는 간단해 보이지만 일반적인 그래프 탐색 알고리즘 보다 고민하고 체크해야할 것이 추가되어 난이도가 꽤 있는 편이다.

중복을 피하기 위해 방문했던 노드를 체크해야 하는데 추가적으로 싸이클에 포함되는 노드라서 방문했던 것인지를 또 확인해야 한다.

 

 

---

 

 

문제의 포인트

 

 

사이클 탐지 알고리즘

 

사이클을 찾는 알고리즘은 몇가지가 있는데 최소 신장 트리를 만들때 사용하는 Union-Find algorithm도 있고 일반적인 그래프 탐색 방법 중 하나인 깊이 우선 탐색 (DFS)를 조금 변형해서도 가능하다.

이 문제의 경우 완성된 그래프가 주어지고 어차피 전체 탐색해야 하기 때문에 DFS를 통해서 찾아가는 방법으로 접근했다.

 

 

우선 DFS를 이용해 주어진 그래프를 중복 방문 없이 탐색할 수 있도록 코드를 짰다.

입력은 각 노드의 순서대로 목적지 노드의 번호만 주어지기 때문에 현재 노드를 index로, 현재 노드가 향하는 노드를 값으로 갖는 배열을 이용했다.

 

void DFS(int s) {
	int next;

	visit[s] = 1;
	next = S[s];

	if (visit[next] == 0) {
		DFS(next);
	}
}

 

 

만약 자기 자신을 목적지로 갖는 노드를 만나는 경우 탐색이 종료되기 때문에 그래프 전체를 탐색하기 위해 전체 노드에 대해 for문으로 탐색 시킨다.

 

 

for (j = 1; j <= N; j++) {
	if (visit[j] < 1) {
    DFS(j);
}

 

 

문제는 여기서 사이클을 찾는 것이다.

다양한 방법이 가능하겠지만 확인용 배열을 하나 더 만든다면 간단히 확인할 수 있다.

 

 

void DFS(int s) {
	int next;

	visit[s] = 1;
	next = S[s];

	if (visit[next] == 0) {
		DFS(next);
	} else {
		if (check[next] == 0) {
        	// 이 안쪽은 이미 방문했지만 (visit[next] != 0)
        	// 탐색 완료되지 않은 노드다 (check[next] == 0)
        	// 즉, 사이클 내에 있기 때문에 return 하지 못하고 다시 시작점으로 온 것이다.
		}
	}
	check[s] = 1; // DFS 탐색을 마치고 return하는 Node는 탐색 완료 여부를 추가 체크해준다.
}

 

 

이렇게 각 노드 탐색 이후 return 직전에 확인했음을 표시해줄 배열을 이용하면 visit 배열과 조합해 사이클에 속하는지 구별할 수 있다.

visit 배열에 의해 이미 방문했던 노드로 확인됐지만 해당 노드의 탐색 완료 표시인 check 배열에 표시가 안되어있다면 탐색을 마치기 전에 이미 방문했던 노드로 돌아왔다는 의미가 된다.

 

 

 

 

위 그림 처럼 탐색해가면서 사이클을 찾을 수 있다.

본 문제는 전체 노드 갯수에서 사이클에 속하는 노드 수를 빼주면 답을 찾을 수 있다.

 

---

 

 

전체 Code

 

#include <iostream>
#include <vector>

using namespace std;

int T, N;
int S[100000 + 10];
int check[100000 + 10];
int visit[100000 + 10];
int cnt;

void DFS(int s) {
	int next;

	visit[s] = 1;
	next = S[s];

	if (visit[next] == 0) {
		DFS(next);
	} else {
		if (check[next] == 0) {
			while (next != s) {
				cnt++;
				next = S[next];
			}
			cnt++;
		}
	}
	check[s] = 1;
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i, j, s, ck;

	cin >> T;

	for (i = 0; i < T; i++) {
		cin >> N;
		cnt = 0;
		for (j = 1; j <= N; j++) {
			cin >> S[j];
			check[j] = 0;
			visit[j] = 0;
		}
		
		for (j = 1; j <= N; j++) {
			if (visit[j] < 1) {
				DFS(j);
			}
		}
		cout << N - cnt << "\n";
	}

	return 0;
}