[백준]10451_순열 사이클

문제

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

이와 같다.

또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해

로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

---

입력

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

---

출력

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

---

예제 입력

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

예제 출력

3
7

---

풀이

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i<T; i++) {
			int cnt = 0;
			int in = Integer.parseInt(br.readLine());
			int [] arr = new int[in+1];
			
			StringTokenizer st = new StringTokenizer(br.readLine());

			for(int j = 1; j<arr.length; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}
			boolean[] visit = new boolean[arr.length];
			
			for(int j = 1; j<arr.length;j++) {
				if(!visit[j]) { //방문하지 않았다면 
					visit[j] = true;
					int go = arr[j]; //연결 된 노드가 있는지 확인 
					while(true) {
						if(visit[go]) {
							cnt++;
							break;
						}
						visit[go] = true; 
						go = arr[go];
					}
				}
			}
			System.out.println(cnt);
		}
		br.close();	
	}
}

• 0번 인덱스는 무시하고 1번 인덱스부터 배열에 숫자를 넣어주었다.
• 반복문을 돌며 해당 인덱스가 false이면 이전에 방문한 적이 없다는 말이니 조건문 안으로 들어간다.

if(!visit[j]) {
	visit[j] = true;

인덱스[j] 값과 해당 arr[j] 값이 서로 연결되어 있는지 확인하기위해 go 변수에 arr[j]값을 담고 if문을 통해 이전에 방문한 적이 있는지 확인한다.

if(visit[go]) {
	cnt++;
	break;
}

방문한 적이 있다면 연결되어있다는 의미로 일단 cnt를 +1한다. > 반복문 탈출

방문한 적이 없다면 방문했다는 의미로 true로 변경하고 이와 또 연결된 노드가 있는지 확인하기위해 go에 arr[go]값을 넣는다.

위의 과정을 반복한다.