[백준][C++] 10451 순열 사이클 - 실버3

문제 보기

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

10451번: 순열 사이클

 

문제                           

 

 

입력                          

 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

 

 

출력                          

 

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

 

 

풀이방법                 

 

푸는 방법은 여러 개가 있을 수 있으나

나는 DFS를 사용해 아주 간단하게 풀었다!

 

순열을 탐색하다 이미 방문 한 노드를 만난다면, 그건 이미 사이클이 완성되었다는 뜻이다.
그리고 한 번도 방문되지 않은 노드를 기점으로 다시 탐색을 시작한다.

 

이렇게 탐색을 시작한 횟수가 얼마인지 구한다면 순열 사이클의 개수도 구할 수 있는 것이다.

 

// 순열 사이클의 개수를 세고 있다.
int count = 0;
for (int i = 1; i <= N; i++)
{
    if (!isVisited[i])
    {
        count++;
        DFS(arr, isVisited, i);
    }
}

// DFS 메서드
void DFS(int* arr, bool* isVisited, int index)
{
	if (isVisited[index])
		return;

	isVisited[index] = true;
	DFS(arr, isVisited, arr[index]);
}

 

아주 기초적인 DFS 지식만 있으면 풀 수 있는 문제.

 

 

 

 

전체 코드

#include <iostream>

using namespace std;

void DFS(int* arr, bool* isVisited, int index);

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

	for (int t = 0; t < T; t++)
	{
		int N;
		cin >> N;
		int* arr = new int[N + 1];
		bool* isVisited = new bool[N + 1];

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

		int count = 0;
		for (int i = 1; i <= N; i++)
		{
			if (!isVisited[i])
			{
				count++;
				DFS(arr, isVisited, i);
			}
		}

		cout << count << endl;

		delete[] arr, isVisited;
	}

	return 0;
}

void DFS(int* arr, bool* isVisited, int index)
{
	if (isVisited[index])
		return;

	isVisited[index] = true;
	DFS(arr, isVisited, arr[index]);
}