백준 10451 순열 사이클(Java)

https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

---

 

해석 및 팁

 

---

 

이 문제는 이해만 하면 어렵지 않게 풀 수 있습니다. 방문확인용 visit 배열을 만든 후 방문한 적이 없으면 방문한 것으로 기록하고 그다음수를 확인하여 방문한 적이 없으면 다시 반복합니다. 총 순회하는 개수를 구해주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {

  static int t;
  static int n;
  static int count;
  static int[] arr;
  static boolean[] visit;
  
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    t = sc.nextInt();
   
    for(int i = 0; i < t; i++) {
      count = 0;
      n = sc.nextInt();
      arr = new int[n+1];
      visit = new boolean[n+1];
      for(int j = 1; j <= n; j++) arr[j] = sc.nextInt();

      for(int j = 1; j <= n; j++) {
        if(visit[j] == false) {      //방문한적이 없으면
          dfs(j);
          count++;
        }
      }
       System.out.println(count);
    }
  }

  public static void dfs(int num) {
    visit[num] = true;                     //방문한것으로 기록
    int next = arr[num];                   //다음값 저장
    if(visit[next] == false) dfs(next);    //다음값도 방문한적이 없으면 재귀
    
  }
}