[백준_10451번] 순열 사이클

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

10451번: 순열 사이클

[문제]

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 그림1과 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

 

그림 1

순열을 배열을 이용해 (1…i…nπ1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다. Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다. N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_10451 {
	static ArrayList<ArrayList<Integer>> graph=new ArrayList<>();
	static int n,result;
	static int[] num;
	static boolean[] visited;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		
		while(t-->0) {
			n=sc.nextInt();
			result=0;
			num=new int[n+1];
			visited=new boolean[n+1];
			
			for(int i=1;i<=n;i++)
				num[i]=sc.nextInt();
			
			for(int i=1;i<=n;i++) {
				if(!visited[i]) {
					cycle(i);
					result++;
				}
			}
			
			System.out.println(result);
		}
	}
	
	static void cycle(int start) {
		visited[start]=true;
		
		if(!visited[num[start]])
			cycle(num[start]);
	}
}

 

[고찰]

 이번 문제는 DFS 알고리즘을 사용하여 그래프의 사이클을 찾는 문제였다. 이전에 풀어봤던 문제였지만 이번에는 이중 연결리스트를 사용하지 않고 풀어보았다.