다희의 코딩 성장일기
[백준] 10451. 순열 사이클 (자바 JAVA) 본문
[ 문제 ] [백준] 10451. 순열 사이클 (자바 JAVA)
문제 링크 : https://www.acmicpc.net/problem/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
'Algorithm > 백준 BOJ' 카테고리의 다른 글
[백준] 1967. 트리의 지름 (자바 JAVA) (0) | 2021.09.27 |
---|---|
[백준] 2800. 괄호 제거 (자바 JAVA) (0) | 2021.09.26 |
[백준] 1254. 펠린드롬 만들기 (자바 JAVA) (0) | 2021.09.23 |
[백준] 1138. 한 줄로 서기 (자바 JAVA) (0) | 2021.09.22 |
[백준] 11725. 트리의 부모 찾기 (자바 JAVA) (0) | 2021.09.20 |
Comments