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

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

2668번: 숫자고르기

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> v;
int N;
int arr[101];
bool visit[101];
void DFS(int start, int cur)
{

	if (visit[cur])
	{
		if (start == cur)
			v.push_back(arr[start]);

		return;
	}
	visit[cur] = true;
	DFS(start, arr[cur]);
}

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

	for (int i = 1; i <=N; i++) {
		memset(visit, false, sizeof(visit));
		DFS(i, i);
	}
	
	sort(v.begin(), v.end());
	cout << v.size() << "\n";
	for (int i = 0; i < v.size(); i++)
		cout<<v[i] << "\n";
}

 

모든 인덱스를 돌며 DFS를 실행합니다

매 탐색마다 visit 배열을 새로 초기화 시켜 줘야합니다.

	for (int i = 1; i <=N; i++) {
		memset(visit, false, sizeof(visit));
		DFS(i, i);
	}

 

DFS( 시작 인덱스, 현재 인덱스 ) 함수를 통해

현재 인덱스의 값을 다음 인덱스로 하여 깊이 탐색을 해줍니다.

방문한 현재 인덱스에 대하여 visit 배열을 통해 방문 체크를 해줍니다.

	visit[cur] = true;
	DFS(start, arr[cur]);

 

이미 방문한 경우에서 시작 인덱스(start) 와 현재 인덱스(cur) 이 같다면 사이클이 발생한겁니다.

왜냐, 이는 현재 모든 탐색한 인덱스와 그 인덱스의 값이 일치하여 사이클이 발생한겁니다.

집합이 같겠죠??

그러므로 처음 시작 인덱스(start)는 집합이 일치하게 만드는 인덱스이므로 v에 담아 줍니다.

	if (visit[cur])
	{
		if (start == cur)
			v.push_back(arr[start]);

		return;
	}

 

 

마지막으로 집합이 가능한 값을 담은 v 배열의 사이즈를 출력해주고

정렬을 통해 오름차순으로 답을 출력하면 됩니다.

	sort(v.begin(), v.end());
	cout << v.size() << "\n";
	for (int i = 0; i < v.size(); i++)
		cout<<v[i] << "\n";