[PS] 텀 프로젝트 / C++ (백준 9466번)

 

간단한 그래프 탐색 문제로 dfs 구현만 잘하면 쉽게 푸는 문제

visit 체크를 해주는 배열에 각 학생들의 상태를 4개로 분리하였다.

 

아래 코드 기준으로 vi[] 배열에 저장된 학생들의 상태는

• -1) cycle을 탐색했지만 팀에 들어가지 못한 상태
•  0) 아직 cycle을 찾아보지 않은 상태
•  1) cycle을 찾아 팀에 들어간 상태
•  2) cycle을 찾는 중인 상태

로 cycle을 탐색하다 next 학생의 vi에 저장된 값이 2(cycle을 찾는 중인 상태)라면 cycle이 완성된 것이므로 next 값을 return 하여 next 학생이 나올 때 까지의 학생들의 상태를 1로 바꿔주고, next 학생이 나오면 그 다음 학생부턴 0 값을 return 하여 상태를 -1로 바꿔주었다.

 

dfs 풀이

#include<iostream>
#include<algorithm>
#include<vector>
int d[100001], vi[100001];

int f(int p) {
	int next = d[p];
	if (vi[next] == 2) {
		vi[p] = 1;
		return next;
	}
	else if (vi[next] == 0) {
		vi[p] = 2;
		int result = f(next);
		if (result) {
			vi[p] = 1;
			if (result == p) {
				return 0;
			}
			else {
				return result;
			}
		}
	}
	vi[p] = -1;
	return 0;
}

int main()
{
	int t, n;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) {
		scanf("%d", &n);
		for (int j = 1; j <= n; j++) {
			scanf("%d", &d[j]);
			if (j == d[j]) vi[j] = 1;
		}

		for (int j = 1; j <= n; j++) {
			if (vi[j] == 1 || vi[j] == -1)continue;
			f(j);
		}

		int dap = 0;
		for (int j = 1; j <= n; j++) {
			if (vi[j] != 1)dap++;
			vi[j] = 0;
		}
		printf("%d\n", dap);
	}
	return 0;
}

 

 

스택을 이용한 풀이

stack으로 구현한 dfs가 이해하기 더 쉬울 것 같았다.

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int d[100001], vi[100001];

int f(int p) {
	int cur = p, cycle_complete = 0;
	stack<int> st;
	while (1) {
		st.push(cur);
		int next = d[cur];
		if (vi[next] == 2) {
			cycle_complete = next;
			break;
		}
		else if (vi[next] == 0) {
			vi[cur] = 2;
			cur = next;
		}
		else break;
	}

	while (!st.empty()) {
		if (cycle_complete != 0)vi[st.top()] = 1;
		else vi[st.top()] = -1;

		if (cycle_complete == st.top())cycle_complete = 0;
		st.pop();
	}

	return 0;
}

int main()
{
	int t, n;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) {
		scanf("%d", &n);
		for (int j = 1; j <= n; j++) {
			scanf("%d", &d[j]);
			if (j == d[j]) vi[j] = 1;
		}

		for (int j = 1; j <= n; j++) {
			if (vi[j] == 1 || vi[j] == -1)continue;
			f(j);
		}

		int dap = 0;
		for (int j = 1; j <= n; j++) {
			if (vi[j] != 1)dap++;
			vi[j] = 0;
		}
		printf("%d\n", dap);
	}
	return 0;
}