10451. 순열 사이클

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

10451번: 순열 사이클

문제 그림만 봐도 11724. 연결 요소의 개수 문제와 상당히 비슷할 것처럼 보였다. 

다른 점은 간선에 방향이 있다는 것?

그래서 그래프를 입력할 때 

a [u]. add(v)

a [v]. add(u)

이런 식으로 양방향을 입력할 필요 없다. 

 

int[] arr = new int[n + 1];
            // arr에 삽입
            for (int i = 1; i < n + 1; i++) {
                arr[i] = s.nextInt();
            }

그냥 이런 식으로 0은 스킵하고 1부터 차례대로 index에 맞춰서 입력했다. 

 

그리고 DFS, BFS를 사용하지 않고 그냥 스택을 이용해 풀었다. 

for (int i = 1; i <= n; i++) {
                if (!mark[i]) {
                    st.push(i);
                    mark[i] = true;
                    cnt++;
                }

                while (true) {
                    int f = st.peek();
                    boolean none = true;
                    int x = arr[f]; // 현재 정점이 가르키고 있는 정점

                    if (!mark[x]) { // 가르키고 있는 정점을 방문한적 없다면
                        st.push(x);
                        mark[x] = true;
                        none = false;
                    }
                    // none이 true라는 것은 가르키는 다음 정점이 이미 방문됨.
                    // 즉 순열 사이클의 끝.
                    if (none) break;
                }

            }

처음 정점 1을 스택에 넣고 그 정점이 가리키는 다음 정점으로 이동한다. 

그렇게 계속 이동하다가 가르키는 다음 정점이 이미 방문한 정점이면 순열 사이클의 끝이라는 것이다. 

 

그다음 정점 2가 이미 방문했다면 스킵하고 방문하지 않았으면 또다시 정점 2에서부터 가리키는 정점으로 이동하면서 순열 사이클의 끝까지 이동한다. 

새로운 순열 사이클 시작할 때마다 cnt값 증가시키면 마지막에 cnt값이 순열 사이클의 개수이다. 

 

코드

import java.util.*;

public class Main {

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);

        int t = s.nextInt(); // test case

        for(int z = 0; z < t; z++) { // while test case~
            Stack<Integer> st = new Stack<Integer>();
            int n = s.nextInt(); // 순열의 크기 n

            boolean mark[] = new boolean[n+1];

            int[] arr = new int[n + 1];
            // arr에 삽입
            for (int i = 1; i < n + 1; i++) {
                arr[i] = s.nextInt();
            }

            int cnt = 0;

            for (int i = 1; i <= n; i++) {
                if (!mark[i]) {
                    st.push(i);
                    mark[i] = true;
                    cnt++;
                }

                while (true) {
                    int f = st.peek();
                    boolean none = true;
                    int x = arr[f]; // 현재 정점이 가르키고 있는 정점

                    if (!mark[x]) { // 가르키고 있는 정점을 방문한적 없다면
                        st.push(x);
                        mark[x] = true;
                        none = false;
                    }
                    // none이 true라는 것은 가르키는 다음 정점이 이미 방문됨.
                    // 즉 순열 사이클의 끝.
                    if (none) break;
                }

            }
            System.out.println(cnt);

        }
    }
}

 

 

---

Solution

 

코드

import java.util.*;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();

        while(k-- > 0) {
            // read vertex size, create vertex
            int n = sc.nextInt();
            ArrayList<Integer>[] a =
                    (ArrayList<Integer>[])new ArrayList[n + 1];
            for(int i = 1; i <= n; i++)
                a[i] = new ArrayList<Integer>();

            // write edge
            for(int i = 1; i <= n; i++) {
                int v = sc.nextInt();
                a[i].add(v); // 하나의 정점에서 하나의 간선만이 존재.
            }

            boolean[] c = new boolean[n + 1]; // mark or check
            int count = 0;
            for(int i = 1; i <= n; i++) { // dfs 탐색
                if(c[i] == false) { // 새로운 탐색 시작
                    count++; // 새로운 연결 요소가 시작되는 셈.
                    dfs(a, c, i);
                }
            }
            System.out.println(count);

        }
    }

    public static void dfs(
            ArrayList<Integer>[] a, boolean[] c, int x) {
        c[x] = true;

        for(int y : a[x]) { // 정점에 연결된 모든 간선 탐색
            if(c[y] == false) dfs(a, c, y);
        }
        
        /* 정점연결 간선 하나뿐이므로 이렇게 해도 됨.
        int y = a[x].get(0); // 정점에 연결된 간선이 하나뿐
        if(c[y] == false) dfs(a, c, y);
         */
    }

}

솔루션에서는 그냥 DFS를 썼다. 

그런데 DFS함수에서 어차피 정점 연결 간선이 하나뿐이므로 

for(int y : a[x]) 이런 식으로 배열의 모든 요소 방문하지 않고

int y = a[x].get(0) 이런 식으로 가장 첫 번째 원소만 갖고 와도 무방하다.