[백준] 10451. 순열 사이클 (자바 JAVA)

[ 문제 ]  [백준] 10451. 순열 사이클 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

---

# 접근 방법 및 풀이 

 

• 그래프 문제다. 처음에는 문제보고 무슨 소리지 했는데 이해하면 바로 풀 수 있다.
• 1~N개까지 숫자를 방향그래프로 나타낼 수 있는데, 그 표현은 다음과 같다. 
• 문제 예시대로 N=8이라면 노드는 1~8번까지 있고, 다음과 같이 배열로 표현할 수 있다.

• 1	2	3	4	5	6	7	8
  3	2	7	8	1	4	5	6

• From과 to로 이해하면 쉽다. 인덱스가 from, 값이 to 이다.
• 1번 노드에서 3번노드로, 3번노드에서 7번노드로, 7번노드에서 5번노드, 5번노드에서 1번노드로 다시 돌아오므로 싸이클이 생긴다.
• 이러한 사이클이 몇개있지 세어주면 정답이다.
• N개만큼 방문체크 배열 visit[ ] 을 만들어, 1번노드부터 순서대로 방문해, 이미 방문한 노드를 다시 방문하게 된다면 싸이클이 생기므로 그때 개수를 증가시켜주면 된다.
• 자세한건 코드참조

# 주의할 점 

 

• 딱히 없음

 

JAVA 코드

package Silver;

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

public class bj10451_순열사이클 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			int ans = 0;
			int size = Integer.parseInt(in.readLine());
			int arr[] = new int[size+1];
			StringTokenizer st = new StringTokenizer(in.readLine());
			for (int i = 1; i < arr.length; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			boolean visit[] = new boolean[size+1];
			for (int i = 1; i < arr.length; i++) {
				if(!visit[i]) {
					visit[i] = true;
					int go = arr[i];
					while(true) {
						if(visit[go]) {
							ans++;
							break;
						}
						visit[go] = true;
						go = arr[go];
					}
				}
			}
			System.out.println(ans);
		}
	}
}

 

 

 

REVIEW