BOJ) 순열 사이클 (10451번)

순열 사이클

10451번: 순열 사이클

1 ~ N 으로 이루어진 순열을 방향 그래프로 나타냈을 때, 몇 개의 사이클이 존재하는지 구하는 문제다.각 Node에서 다음 Node의 vertex를 가지고 있고, 이 정보가 주어지기 때문에 배열을 활용했다.또한, find-union에서 착안하여 연결되는 지점을 DFS로 찾아가며 문제를 해결했다.

 

사이클을 형성하는지 확인하는 isCycle 메소드를 만들어 주었다.return 값은 boolean 형태이며, 이어진 Node를 순회하다가, 재방문하게되면 true를, 아니면 false를 리턴해주었다.

 

isCycle 메소드 만으로는 캐치할 수 없는 경우가 있다.

빠른 이해를 위해 아래 그림을 통해 설명을 대체하겠다.

 

사이클에 연결된 경우

 

사이클이 아니었던 곳에 연결된 경우

 

사이클이든 아니든, 이미 경로 탐색을 마친 경우다.

이 경우, isCycle이 true를 반환할 것이다.

따라서, isCycle인지 검증하기 전에 parents[now.vertex]를 방문했는지 여부를 먼저 체크해서, 방문한 적이 있다면, 방문 처리를 해주었다.

사이클에 해당 노드가 들어가든 아니든지간에 사이클의 숫자를 늘릴 경우가 아니기 때문이다.

 

코드

 

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

public class PermutationCycle_10451 {
  static int[] parents;
  static boolean[] visit;

  public static void main(String[] args) throws IOException {
    final String NEW_LINE = "\n";
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int testCases = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();

    while(testCases-- >0) {
      int n = Integer.parseInt(br.readLine());
      init(n, br.readLine());
      sb.append(solution(n)).append(NEW_LINE);
    }

    br.close();
    System.out.println(sb.toString());
  }

  private static int solution(int n) {
    int answer =0;
    for(int i=1; i<=n; i++) {
      if(!visit[i]) {
        if(visit[parents[i]]) {
          visit[i] = true;
        } else {
          if (isCycle(i)) {
            answer++;
          }
        }
      }
    }
    return answer;
  }

  private static void init(int n, String graphStr) {
    StringTokenizer st = new StringTokenizer(graphStr);
    parents = new int[n+1];
    for(int i=1; i<=n; i++) {
      parents[i] = Integer.parseInt(st.nextToken());
    }
    visit = new boolean[n+1];
  }

  private static boolean isCycle(int val) {
    if(!visit[val]) {
      visit[val] = true;
      return visit[parents[val]] ? true : isCycle(parents[val]);
    }
    return false;
  }
}