🖊️ 문제

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

🖊️ 풀이

또 DFS 문제....
너무사랑하는듯...

그냥 배열에 저장해놓고, 해당 배열값으로 시작값과 같아질 때까지 넣어주면 된다!

어렵지 않은 문제였지만, 쟁점은
1. 방문 체크를 하되, 백트래킹을 할 수 있도록 하는 것 (4->5 에서 실패했지만, 5를 탐색할 수 있도록)
2. 중복된 것들도 다 넣고, unique로 중복 원소들을 제거해주는 것.

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

int arr[101];
bool visited[101] = { false, };
vector<int> vec;

void DFS(int start, int cur, vector<int> v)
{
	if (visited[cur]) return;
	if (start == arr[cur]) {
		for (int& e : v)
			vec.push_back(e);
		return;
	}
	visited[cur] = true;
	v.push_back(arr[cur]);
	DFS(start, arr[cur], v);
	visited[cur] = false;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			vector<int> v;
			v.push_back(i);
			DFS(i, i, v);
		}
	}

	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	cout << vec.size() << endl;
	for (int& e : vec)
		cout << e << endl;
}