[Problem Solving] BOJ 10451 : 순열 사이클

문제 링크 : https://www.acmicpc.net/problem/10451

 

i -> P[i]로 그래프가 만들어 졌을 때, 사이클의 수를 구하는 문제이다. 

 

사이클은 DFS로 찾을 수 있는 데, 일단 visited부터 정의해야한다.

visited[i] = 0 은 아직 방문하지 않은 노드

visited[i] = 1 DFS 호출 스택에 있는 노드

visited[i] = 2 방문 한 노드

이다. 

DFS 수행 중에 visited[i]가 1인 노드가 인접 노드라면 사이클을 탐지한 것이기 때문에 answer를 1 증가시킨다.

 

1. i = 1 ~ N까지 visited[i] == 0인 i에 대해 dfs(i)를 호출한다.

2. dfs(s)에서 visited[s] 를 1로 설정하고 인접한 노드 중에 visited[next] == 0인 next에 대해 dfs(next)를 호출한다. 인접한 노드 중에 visited[next] == 1이 있다면 answer를 1증가시킨다.

3. visited[s]를 2로 설정한다.

4. answer를 출력한다.

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

public class Main 
{
    public static int N;
    public static int[] P;
    public static int answer;
    public static ArrayList<ArrayList<Integer>> graph;
    public static int[] visited;

    public static void input(BufferedReader br) throws IOException
    {
        N = Integer.parseInt(br.readLine());
        P = new int[N + 1];
        String[] temp = br.readLine().split(" ");
        for(int i = 1; i <= N; i++)
        {
            P[i] = Integer.parseInt(temp[i - 1]);
        }
        answer = 0;
    }

    public static void dfs(int s)
    {
        visited[s] = 1;
        for(int next : graph.get(s))
        {
            if(visited[next] == 0)
            {
                dfs(next);
            }
            else if(visited[next] == 1)
            {
                ++answer;
            }
        }
        visited[s] = 2;
    }

    public static void solution()
    {
        visited = new int[N + 1];
        graph = new ArrayList<ArrayList<Integer>>(N + 1);
        for (int i = 0; i <= N; i++)
        {
            graph.add(new ArrayList<Integer>());
        }
        for (int i = 1; i <= N; i++) 
        {
            visited[i] = 0;
            graph.get(i).add(P[i]);
        }

        for(int i = 1; i <= N; i++)
        {
            if(visited[i] == 0)
            {
                dfs(i);
            }
        }
    }

    public static void output()
    {
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++)
        {
            input(br);
            solution();
            output();
        }
        br.close();
    }
}