[BOJ] 2668번_숫자고르기_DFS (C++)

[문제]

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

첫째 줄에는 1부터N이 차례로 들어 있고, 둘째 줄에는 1이상 N이하인 정수가 무작위로 들어 있다. 이 때 첫째 줄에서 숫자를 적절히 뽑으면, 첫째 줄에서 뽑은 집합과 첫째 줄 바로 아래의 둘째 줄에 들어있는 숫자의 집합이 일치한다. 이러한 조건을 만족하면서 가장 많은 정수를 가진 집합을 만드는 문제이다.

[사용 알고리즘]

DFS(깊이 우선 탐색)

[풀이 핵심]

• DFS를 돌며 처음 시작한 노드와 끝나는 노드가 일치할 때 result벡터에 추가해준다.

  문제에 주어진 예제를 통해 설명하자면. 첫째 줄의 1을 선택했을 때, 1(첫째 줄)->3(둘째 줄), 3(첫째 줄)->1(둘째 줄) 이런식으로 사이클이 생성되면 해당 숫자를 고르고 result벡터에 추가해주면된다.

[코드]

//boj2668번_숫자고르기_그래프

#include<iostream>
#include<vector>

using namespace std;

int graph[101];
int visited[101];

vector<int> result;

void DFS(int V, int first_V) {
	if (visited[V]) {
		if (V == first_V) {
			result.push_back(V);
		}
		return;
	}

	visited[V] = true;
	DFS(graph[V], first_V);
}

int main() {
	int N;
	cin >> N;

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

	for (int i = 1; i <= N; i++) {

		for (int j = 0; j < 101; j++) {
			visited[j] = false;
		}

		DFS(i, i);
	}

	cout << result.size() << '\n';

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << '\n';
	}

	return 0;
}