[BOJ] 10451. 순열 사이클

7315 단어 DFS알고리즘DFS

풀이

#include <iostream>
#include <string.h>

using namespace std;

int TC, N;
int map[1001];
int is_visit[1001];
int start, finish, cnt = 0;

void init();
void dfs(int n);

int main(){
	cin >> TC;
	for(int t = 0; t < TC; t++){
		init();
		for(int i = 1; i <= N; i++){
			start = i;
			if(!is_visit[i]) dfs(i);
		}
		cout << cnt << endl;
	}
}

void init(){
	memset(map, 0, sizeof(map));
	memset(is_visit, 0, sizeof(is_visit));
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> map[i];
	}
	cnt = 0;
}

void dfs(int n){
	is_visit[n] = 1;
	if (is_visit[map[n]]){
		if(map[n] == start) cnt ++;
		return;
	}
	dfs(map[n]);
}

전보다 코드는 간결해지고 풀이 시간은 짧아졌다.

좋은 웹페이지 즐겨찾기