[백준 2668번] 숫자 고르기 - JAVA

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

2668번: 숫자고르기

풀이

사용한 알고리즘 : DFS

 

풀이전략

싸이클이 발생하는 노드들을 모아 오름차순으로 출력해주면 되는 문제다.

1. DFS를 통해 각 노드마다 싸이클이 발생하는지 판단한다.

    - DFS 탐색 중, 탐색의 첫 번째 노드와 동일한 노드로 탐색을 하게 되면 싸이클이다.

2. 싸이클이 발생하면 탐색과정의 모든 노드 번호들을 TreeSet에 삽입한다.

3. 첫번째 노드부터 마지막 노드까지 2번 과정을 반복한다.

4. TreeSet의 원소들을 차례로 출력한다.

 

제출코드

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

public class Main {

    static boolean visited[];
    static int graph[];
    static TreeSet<Integer> result = new TreeSet<>();
    static LinkedList<Integer> temp = new LinkedList<>();

    static void dfs(int x){
        visited[x]=true;
        temp.add(x);

        if(temp.get(0)==graph[x]){
            result.addAll(temp);
            return;
        }

        if(!visited[graph[x]]){
            dfs(graph[x]);
        }
    }


    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        visited=new boolean[N+1];
        graph=new int[N+1];

        for(int i=1;i<N+1;++i){
            graph[i]=Integer.parseInt(br.readLine());
        }

        for(int i=1;i<N+1;++i){
            temp.clear();
            Arrays.fill(visited,false);
            dfs(i);
        }

        System.out.println(result.size());
        for(Integer x:result){
            System.out.println(x);
        }
    }
}