[백준 2668] 숫자고르기 (C++)

문제 링크: https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

1. 주의할 점

- 그래프로 생각 -> DFS로 접근 -> 중복된 숫자 처리

 

2. 구현

- 그래프로 생각하여 Arr[]배열에 1~Num까지 가리키는 Node의 번호를 입력 받는다

- 각 Node마다 시작하여 첫 시작점을 기준으로 순환하는 형태가 이루어진다면 Ans 벡터에 담는다(단, 이미 1번 이상 담은 Node는 넣지 않는다)

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[101], num, start;
bool visit[101];
bool check[101] = { false, };
vector<int> ans;

void dfs(int idx) {
	//되돌아 오는 경우
	if (idx == start && visit[idx]) {
		for (int i = 1; i <= num; i++)
			if (visit[i] && !check[i]) {
				ans.push_back(i);
				check[i] = true;
			}
		return;
	}
	if (visit[idx]) return;
	visit[idx] = true;
	int next = arr[idx];
	dfs(next);
}

int main() {
	cin >> num;
	for (int i = 1; i <= num; i++)
		cin >> arr[i];
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= num; j++)
			visit[j] = false;
		start = i;
		dfs(i);
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << "\n";
	system("pause");
	return 0;
}