[자바] 백준 1115 - 순열 (boj java)

문제 : boj1115

 

  오랜만에 엄청 잘만들었다고 느낀 문제였다. 아이디어 문제이다. 해설은 간단한데, 사실 이걸 떠올리는게 전부인 문제이다.

 

1. B[0] = 0 이므로 즉 A[0]부터 시작한다고 보면 된다.

2. B[i]=A[B[i-1]] 은 즉 A[0]부터 시작한댔으니, A[0] -> A[A[0]] -> A[A[A[0]]] 이런식으로 진행하겠다는 의미이다.

 

  이 때 이게 순열이 되려면 결국 중간에 끊기지 않고 모든 A원소들을 들릴 수 있어야 한다.

그럼 당연히 처음 입력된 A가 모두 들릴 수 있다면? 그냥 0으로 끝이다.

중요한건 중간에 끊길 경우, 어떻게 최소로 교환해서 전체를 들릴 수 있도록 만들 것인지가 관건이다.

 

  직관적으로 이걸 그래프로 생각해보면 좀 더 생각하기 편한데, 결국 끊겼다는 것은 전체 원소를 포함하지 않는 사이클이 생겼다는 얘기가 된다. 그럼 여러 사이클이 있을 때 이 사이클을 가장 간단하게 끊을 수 있는 방법을 생각하면 된다.

 

  일단 그려보고 생각해보면 규칙을 찾을 수 있다. 예제 입력 1과 예제 입력 4를 그래프로 바꿔서 표현한게 검정색으로 그려둔 것이다. 각 사이클을 끊기 위해서는, 사이클의 간선 하나를 변경해서 다른 사이클을 가르키게(주황색) 하면 된다.

  즉, 주어진 순열에서 생기는 사이클이 몇 개 인지만 세면 그 사이클의 수가 답인 셈이다(하나의 사이클 제거를 위해 하나의 간선을 변경해야 하므로). 주의점은 사이클이 1개일때는 당연히 그 자체가 답이므로 1이 아니라 0을 출력해줘야 한다.

 

 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
        boolean[] v = new boolean[n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (v[i]) continue;
            cnt++;
            int s = i;
            while (!v[s]) {
                v[s] = true;
                s = arr[s];
            }
        }
        System.out.println(cnt==1?0:cnt);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}