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

06 Oct 2023 in Algorithm on 그래프 이론

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

풀이

사이클을 찾는 문제이다.

arr[i] -> arr[arr[i]]

이런식으로 뽑힌 정수를 인덱스로 하는 숫자를 다시 봐야한다.

처음 시작한 숫자와 같은 숫자가 나오면 사이클이 완성된다.

dfs탐색을 통해 뽑힌 정수를 인덱스로 하여 탐색했고 처음 숫자가 나왔을 때 list에 넣었다.

---

메모리: 14216KB

시간: 128ms

언어: Java 11

코드

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

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

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

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

        list = new ArrayList<>();
        visit = new boolean[N + 1];
        for (int i = 1; i < N + 1; i++) {
            visit[i] = true;
            dfs(i, i);
            visit[i] = false;
        }

        Collections.sort(list);
        System.out.println(list.size());
        list.stream().forEach(System.out::println);
    }

    private static void dfs(int idx, int st) {
        if (arr[idx] == st) {
            list.add(st);
        }

        if (!visit[arr[idx]]) {
            visit[arr[idx]] = true;
            dfs(arr[idx], st);
            visit[arr[idx]] = false;
        }
    }

}