[백준 10451] 순열 사이클

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

DFS문제입니다. 

숫자고르기랑 비슷하지만 이건 사이클 자체의 갯수만 세면 되기때문에 

1번부터 N까지 돌리면서 처음 방문한다면

사이클 갯수 1늘리고 방문체크하고 DFS로 방문체크만 하고 나오면 됩니다.

 

처음 풀때는 숫자고르기랑 똑같이 해서 통과했습니다. (visited가 2까지 가는경우로 체크방법)

제출 후 보니까 속도가 딱 2.5배 오래걸리더군요.

그래서 지금 올린 소스로 다시 통과했습니다.

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class Q10451_ver2 {
	static int[] arr;
	static int[] visited;
	static int cnt;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	int testCase = Integer.parseInt(br.readLine());
	for(int j=0; j<testCase; j++) {
	cnt = 0;
	int nodeNum = Integer.parseInt(br.readLine());
	arr = new int[nodeNum+1];
	visited = new int[nodeNum+1];
	st = new StringTokenizer(br.readLine());
	for(int i=1; i<arr.length; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
	}
	for(int i=1; i<arr.length; i++) {
	if(visited[i]==0) {
	cnt++;
	dfs(arr, i);
	}
	}
	System.out.println(cnt);
	}
	}
	public static void dfs(int[] arr, int num) {
	int next = arr[num];
	if(visited[next]==1) {
	return;
	}
	visited[next]++;
	dfs(arr, next);
	}
	}

view raw Q10451.java hosted with ❤ by GitHub