[백준][dfs][Java] 2668. 숫자 고르기 : 골드 5

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

 

이 문제는 선택한 수들의 집합이 다시 자기 자신을 가리키는 구조인지를 확인하는 문제다.
즉, 단순히 몇 개의 숫자를 고르는 것이 아니라, 선택한 숫자들만 따라가도 다시 원래 출발한 숫자로 돌아올 수 있어야 한다.

예를 들어

1 2 3 4 5
5 6 1 1 3

 

이때 1, 3, 5를 선택하면, 각 숫자가 가리키는 값도 5, 1, 3이 되어 다시 같은 집합이 된다.

 

이를 그래프로 보면 1 -> 5 -> 3 -> 1 과 같이 연결되고, 결국 다시 시작점으로 돌아오는 사이클이 만들어진다.

이처럼 어떤 숫자를 선택했을 때, 그 숫자에서 출발해서 계속 따라가면 다시 자기 자신으로 돌아와야 정답에 포함될 수 있다.

그래서 이 문제는 각 숫자를 시작점으로 DFS를 수행하며, 자기 자신으로 다시 돌아오는지 확인하는 방식으로 해결할 수 있다.

즉, i에서 출발해서 탐색을 진행했을 때 다시 i로 돌아오면, 그 숫자 i는 사이클에 포함된 것이므로 정답에 넣는다.

 

[코드 풀이]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class Main{
    static int N;
    static int[] arr;
    static boolean[] visited;
    static ArrayList<Integer> list;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

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

        list = new ArrayList<>();
        visited = new boolean[N+1];

        for(int i = 1; i < N+1; i++){
            visited[i] = true;
            dfs(i, i);
            visited[i] = false;
        }

        Collections.sort(list);
        System.out.println(list.size());
        for(int num : list){
            System.out.println(num);
        }
    }

    public static void dfs(int index, int start){
        if(arr[index] == start){
            list.add(start);
        }

        if(!visited[arr[index]]){
            visited[arr[index]] = true;
            dfs(arr[index], start);
            visited[arr[index]] = false;
        }
    }
}