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

 

www.acmicpc.net/problem/2668

2668번: 숫자고르기

[문제 풀이]

DFS를 이용하여 문제를 풀었습니다.

 

이 문제는 배열을 적절히 선택 했을 때 배열의 인덱스와 배열의 값이 같은 최대 크기의 집합을 찾는 문제입니다. 이 문제의 로직은 싸이클을 찾는 문제와 비슷합니다. 배열의 값을 타고 들어갔을 때 배열의 인덱스로 다시 돌아오는지 하면 됩니다. 

 

코드 설명

• 배열의 값을 exist 배열에 저장해 둡니다.
• 입력 받은 배열을 순회 하면서 exist에 저장되 있는 값이라면 싸이클을 찾아줍니다.

[코드]

#include<iostream>
#include<vector>

using namespace std;

int N;

int arr[101];
int exist[101];
int visit[101];


bool DFS(int start, int from, int to) {

	if (start == to)
		return true;

	if (visit[to] == 1)
		return false;
	
	visit[to] = 1;
	return DFS(start, to, arr[to]);

}

int main() {

	cin >> N;

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

	vector<int> answer;

	for (int i = 1; i <= N; i++)
		if (exist[i] == 1) {

			for (int j = 1; j <= N; j++)
				visit[j] = 0;

				if (DFS(i, i, arr[i]))
					answer.push_back(i);
		}

	cout << answer.size() << endl;

	for (auto item : answer)
		cout << item << endl;

	return 0;

}