2668. 숫자고르기

문제 개요

N개의 숫자와 대응하는 숫자가 주어졌을 때 서로 연결된 숫자들을 구하는 문제입니다.

문제 접근

각 숫자들은 하나의 숫자만을 가지기 때문에 자기 자신을 포함하거나 포함하지 않는 경로가 만들어질 수 있습니다.
따라서 첫 번째 DFS를 통해 경로의 시작 위치를 파악하고 두 번째 DFS를 통해 경로를 구성하는 숫자들을 모두 구할 수 있습니다.

HashSet이 정렬된 상태로 저장되는 것이 아니라는 것을 몰라서 틀렸던 문제였습니다.

소스 코드

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

public class Main {
    static int N;
    static int[] nums;
    static void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        nums = new int[N+1];
        for(int i=1;i<=N;i++){
            nums[i] = Integer.parseInt(bf.readLine());
        }
    }

    static Set<Integer> getCycleNodes(int node){
        Set<Integer> nodes = new HashSet<>();
        while(!nodes.contains(node)){
            nodes.add(node);
            node = nums[node];
        }
        nodes.clear();
        while(!nodes.contains(node)){
            nodes.add(node);
            node = nums[node];
        }

        return nodes;
    }

    static void process(){
        Set<Integer> nodes = new HashSet<>();
        for(int i=1;i<=N;i++){
            nodes.addAll(getCycleNodes(i));
        }
        System.out.println(nodes.size());
        nodes.stream().sorted().forEach(System.out::println);
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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