[백준/BOJ] 백준 2668번 : 숫자고르기

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

2668번: 숫자고르기

표의 첫째줄 번호에서 둘째줄 번호로 가는 간선을 만들어 그래프를 만들면, 뽑힌 첫째줄의 집합과 둘째줄의 집합이 일치하는 것은 한 번호에서 시작해서 다시 자신의 번호로 돌아올 때 그 경로의 노드들이 이러한 집합을 이룬다는 것을 알 수 있다. 그러므로 1~n번 노드에서 시작하는 경우를 모두 고려해서 해당하는 노드들을 구한다

 

코드

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

vector<vector<int>> adj(101);
int n;
bool visited[101];

//start:탐색을 시작한 위치, here: 현재위치, selected:지금까지 고른 노드 
//start위치에서 시작해서 다시 start위치까지 오면 그동안 고른 노드들을 반환한다
vector<int> Solve(int start, int here, vector<int>& selected)
{
	vector<int> ret;

	//here 위치에 인접한 노드들을 탐색한다
	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		//there가 시작 지점일때
		//그동안 고른 노드 목록을 반환한다
		if (there == start)
		{
			return selected;
		}

		//there가 방문한 적이 없다면, 방문한다
		if (visited[there] == false)
		{
			//there을 고르고 방문한다
			selected.push_back(there);
			visited[there] = true;
			ret = Solve(start, there, selected);

			//빈 벡터가 아닌 노드 목록은 반환 했다면
			//시작 지점으로 돌아 온것을 성공한것이므로 이 목록을 반환한다 
			if (ret.size() != 0)
				return ret;

			//there가 아닌 다른 인접한 노드들을 확인해 본다
			selected.pop_back();
			visited[there] = false;
		}
	}

	return ret;
}

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

	int temp;
	set<int> result;
	set<int> ::iterator it;
	vector<int> result_i;
	vector<int> selected;

	cin >> n;

	//노드 i에서 temp로 가는 간선을 만든다
	for (int i = 1; i <= n; i++)
	{
		cin >> temp;
		adj[i].push_back(temp);
	}

	//i~n노드를 시작 정점으로 하는 깊이 우선 탐색을 한다
	for (int i = 1; i <= n; i++)
	{
		memset(visited, 0, sizeof(visited));
		selected.clear();

		//i노드에서 시작하므로 i노드를 선택 노드 목록에 넣는다
		selected.push_back(i);

		//i번째 노드에서 시작했을때 i로 돌아오는 경로의 노드들
		result_i = Solve(i, i, selected);

		//result는 set이므로 중복된 수를 저장하지 않고 정렬 되어서 저장된다
		for (int i = 0; i < result_i.size(); i++)
			result.insert(result_i[i]);
	}


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

	for (it = result.begin(); it != result.end(); it++)
	{
		cout << *it << "\n";
	}

	return 0;
}