[백준 / Java] 2668 숫자고르기

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

 

---

 

문제 개요

 가로로 N개의 칸, 세로로 두 줄로 이루어진 표가 주어진다. 첫 번째 줄에는 1부터 N까지의 정수가 순서대로 들어 있으며, 두 번째 줄에는 각 칸마다 1 이상 N 이하의 정수가 하나씩 주어진다. 이때, 첫 번째 줄에서 일부 정수를 선택하되, 선택한 정수들의 집합과 각 정수 바로 아래 칸에 위치한 수들의 집합이 정확히 일치하도록 해야 한다.

 

접근 방법

 

• 이 문제는 "S와 T가 같아야 한다"는 조건이 정확히 '자기 자신으로 돌아오는 사이클'이라는 성질을 의미
• 예를 들어 1 → 3 → 1이면 S={1,3}, T={3,1} → 동일하므로 조건 성립

 

코드

 

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
    static int N;
    static int[] arr;
    static boolean[] v;
    static boolean[] ansV;
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        init();
        for (int i = 0; i < arr.length; i++) {
            v = new boolean[N+1];
            cycle(i, i);
        }

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

    public static void cycle(int start, int cur) {
        if(!v[cur]) {
            v[cur] = true;
            cycle(start, arr[cur]);
        } else {
            if(start == cur) {
                for(int i=1; i<=N; i++) {
                    if(v[i] && !ansV[i]) {
                        list.add(i);
                        ansV[i] = true;
                    }
                }
            }
        }
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        ansV = new boolean[N+1];

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