알고리즘(C++) / 백준 10451 : 순열 사이클

10451

boj.kr/10451

10451번: 순열 사이클

 

문제

 

입력

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

 

출력

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

 

코드

//10451 순열사이클
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[1001] = { 0, };
bool visited[1001] = { false, };
int cycle = 0;

void DFS(int node) {
	visited[node] = true;
	int next = arr[node];
	if (visited[next] != true) {
		DFS(next);
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T, N;
	cin >> T;

	int num;
	for (int i = 0; i < T; i++) {
		cin >> N;

		fill(visited, visited + 1001, 0);
		fill(arr, arr + 1001, 0);
		cycle = 0;

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

		for (int k = 1; k <= N; k++) {
			if (visited[k] == false) {
				DFS(k);
				cycle++;
			}
		}
		cout << cycle << "\n";
	}
	return 0;
}

 

설명

순열 사이클 개수를 구해야한다.

입력받은 순열은 다음 노드를 가리킨다.

즉, (3, 2, 1) 순열은 1번 노드가 3번을 가리키고, 2번 노드는 2번 노드를 가리키고, 3번 노드는 1번을 가리킨다.

 

arr 배열에 입력받은 순열을 1번배열부터 저장한다. 

방문하지 않은 노드들을 차례대로 방문하고 DFS에서 next 노드를 방문한다. 만약 next가 이미 방문한 노드라면 cycle이라고 할 수 있다. 연결되어있는 모든 노드들을 방문하여 cycle을 증가시킨다. 

 

연결되어있는 노드는 무조건 한사이클이다. 

 

결과

 

고찰

DFS로 구현할 수 있었다. 

초기화를 안해서 자꾸... 출력에 오류가... 난다...

 

난이도

●○○○○