백준 10451, 순열 사이클(java)

문제 풀이

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

10451번: 순열 사이클

1부터 N까지 노드가 있을 때 해당 숫자와 연결된 배열이 주어진다. 여기서 순열 사이클의 수를 찾는 문제이다.

문제 풀이

첫 번째 풀이

처음에는 간단하게 반복문으로 풀어줬다. 시작하는 노드 start와 그래프를 탐색하면서 변하는 현재 노드 current, 그리고 현재 노드와 연결된 다음 노드 next를 이용했다. 계속해서 next를 이용해서 다음 노드로 이동하는데, 만일 next가 start와 같아서 사이클이 완성된다면 반복문을 탈출한다.

 

여기서 중요한 게 visit를 boolean 배열로 두고 위의 반복문을 진행하며 방문 표시를 해서 이미 사이클에 들어가 있는 노드는 탐색하지 말아야 한다.

    public static void graph (int start) {
        visit[start] = true;
        int current = start;

        while (true) {
            int next = arr[current];
            if (next == start) {
                return;
            }

            visit[next] = true;
            current = next;
        }
    }

두 번째 풀이

위의 반복문을 재귀로 풀어줬다.

    public static void dfs(int current) {
        if (visit[current]) {
            return;
        } else {
            visit[current] = true;
            dfs(arr[current]);
        }
    }

코드

java

import java.util.*;
import java.io.*;

public class Main {
    public static int[] arr;
    public static boolean[] visit;

    public static void graph (int start) {
        visit[start] = true;
        int current = start;

        while (true) {
            int next = arr[current];
            if (next == start) {
                return;
            }

            visit[next] = true;
            current = next;
        }
    }

    public static void dfs(int current) {
        if (visit[current]) {
            return;
        } else {
            visit[current] = true;
            dfs(arr[current]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        int answer = 0;

        for (int i=0; i< t; i++) {
            int n = Integer.parseInt(br.readLine());
            arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<n; j++) {
                arr[j] = Integer.parseInt(st.nextToken())-1;
            }
            visit = new boolean[n];
            answer = 0;
            for (int j=0; j<n; j++) {
                if (!visit[j]) {
                    answer++;
                    //graph(j);
                    dfs(j);
                }
            }
            System.out.println(answer);
        }
    }

}