[백준/C++] 2668번 숫자고르기

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

2668번: 숫자고르기

문제풀이

dfs문제이다.

알맞은 조합을 고르는 법은 다음과 같다.

1	2	3
3	1	2

위 테이블에서 처음 인덱스 1 -> arr[1]은 3 -> 인덱스 3 -> arr[3]은 2 -> 인덱스 2 -> arr[2]는 1 순서로 탐색을 진행한다.

만약 이 때, 처음 인덱스로 돌아온다면 조건을 만족시키도록 수를 뽑을 수 있는 경우인 것이다!

이 경우에는 pivot만을 저장해주고, i를 1 증가시켜서 그 다음 인덱스에 대해 탐색을 진행한다. 즉, 해당 pivot에서 dfs탐색하였는데 사이클이 만들어진다면 뽑아도 되는 수인 것이다.

대신, 모든 수에 대해서 탐색을 진행해줘야한다. 사이클이 하나 형성되었다고 바로 종료하면 당연히 틀리게 될 것..!

정답코드

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n;
int arr[101];
bool visited[101];
vector<int> ans;

void dfs(int pivot, int cur) {
	if (!visited[cur]) {
        visited[cur] = true;
		dfs(pivot, arr[cur]);
	}
	else if (cur == pivot) {
		ans.push_back(pivot);
		return;
	}
}

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

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

	for (int i = 1; i <= n; i++) {
		memset(visited, false, sizeof(visited));
		dfs(i, i);
	}

	cout << ans.size() << '\n';
	for (auto o : ans) {
		cout << o << '\n';
	}
    return 0;
}