BaekJoon 10451번: 순열 사이클(C++)

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

10451번: 순열 사이클

풀이법

1) DFS를 활용하여 최소를 구하는 문제이다.

2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다.

3) stack을 활용하여 dfs를 구현하였으며, 다음의 노드가 이미 방문되었다면 cycle이 있는 것이다.

4) cycle로 새로운 값을 넣을 때는 for문을 활용하여 방문하지 않은 값을 넣은 후, break 해 주었다.

			for (int i = 1; i <= n; i++)
			{
				if (!visited[i])
				{
					visited[i] = true;
					st.push({ arr[i],arr2[i] });
					break;
				}
			}

break 해주지 않으면, 기존에 방문하지 않은 visited 배열이 다 참이 되어버리기에, 방문 하지 않은 노드 한 개만 넣고 다시 사이클을 찾는 방식으로 구현하였다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;

int t;
int n;
int arr[1001];
int arr2[1001];
bool visited[1001];
int dfs()
{
	stack<pair<int,int>> st;
	visited[1] = true;
	int cnt = 0;
	st.push({arr[1],arr2[1] });
	while (!st.empty())
	{
		int now = st.top().first;
		int next = st.top().second;
		st.pop();
		if (visited[next])
		{
			cnt++;
			for (int i = 1; i <= n; i++)
			{
				if (!visited[i])
				{
					visited[i] = true;
					st.push({ arr[i],arr2[i] });
					break;
				}
			}
		}
		else
		{
			visited[next] = true;
			st.push({ arr[next],arr2[next] });
		}
	}
	return cnt;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	for (int p = 0; p < t; p++)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			visited[i] = false;
			int a;
			arr[i] = i;
			cin >> a;
			arr2[i] = a;
		}
		int c;
		c=dfs();
		cout << c<<"\n";
	}
}