[Baekjoon] 10451_순열 사이클

Silver III

문제(출처: https://www.acmicpc.net/problem/10451)

---

< 순열 사이클 >

 

문제 풀이 

 

dfs를 통해 순열 사이클의 개수를 구한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _10451_ { // 순열 사이클
	static int arr[];
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());
		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());
			arr = new int[n + 1];
			visited = new boolean[n + 1];

			st = new StringTokenizer(bf.readLine());
			for (int j = 1; j <= n; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}

			int cnt = 0;
			for (int j = 1; j <= n; j++) {
				if (!visited[j]) {
					cnt += 1;
					visited[j] = true;
					dfs(j);
				}
			}
			bw.write(cnt + "\n");
		}
		bw.flush();
	}

	private static void dfs(int j) {
		if (!visited[arr[j]]) {
			visited[arr[j]] = true;
			dfs(arr[j]);
		}
	}
}

변수)
t : 테스트 케이스 수
n : 순열의 크기
arr : 순열
visited : 방문 여부
cnt : 순열 사이클의 개수

 

테스트 케이스 수를 입력받아 테스트 케이스 수만큼 아래 과정을 반복한다.

1) 순열의 크기를 입력받아 순열의 크기만큼 순열을 입력받아 arr에 저장한다. 

2) 순열을 탐색하면서 아직 방문하지 않은 순열을 방문 후 dfs 함수를 호출한다.

3) dfs 함수를 호출한 횟수가 순열 사이클의 수 이므로 cnt를 출력한다.

 

dfs (int j)

아직 방문하지 않은 곳이라면 방문 및 dfs를 호출한다.

---

---