DFS 백준 알고리즘 자바 10451 ‘순열 사이클’ 문제풀이

Problem

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

순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 “순열 사이클” 이라고 한다. N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

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

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

Solution

이해를 하면 아주 쉬운 문제이다. 꼭 백준 사이트에서 그림을 보며 이해하길! 배열에서 첫번째 줄은 1,2,3…. 인덱스 값으로 생각하고, 두번째 줄 3,2,7,…을 배열의 값으로 생각해 arr[]로 두었다. 인덱스와 배열의 값이 연결될 수 있으며, 위에서 보이듯이 인덱스 1은 arr[1]과 연결되어 있고, 그것은 또 arr[3]과 연결되어 있고…. 연결된 마지막까지 찾아가는 문제이므로 DFS로 풀었다. 인덱스 i와 arr[i] 값이 같으면 자기 자신만 잇는 그래프가 된다. 그래서 1을 리턴해준다. 방문한 곳을 들렸다는 의미도 그래프가 처음 지점으로 돌아갔다, 즉 사이클이 완성되었다는 의미이므로 리턴 1을 해준다. 그 리턴값들을 모두 더하면 그래프의 개수가 된다.

Code

import java.util.Scanner;
public class Main {
	static int[] arr;
	static boolean[] v;
	static int n;
	public static int dfs(int i) {
		if(i == arr[i] || v[i]) return 1;
		
		v[i] = true;
		return dfs(arr[i]);
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int tc = scan.nextInt(), cnt;
		
		for(int i = 0; i < tc; i++) {
			n = scan.nextInt(); cnt =0;
			arr = new int[n+1]; v = new boolean[n+1];
			for(int j = 1; j < n+1; j++)
				arr[j] = scan.nextInt();
			
			for(int j = 1; j < n+1; j++) {
				if(!v[j]) cnt += dfs(j);
			}
			System.out.println(cnt);
		}
	}
}