[BOJ2668] 숫자고르기

문제 설명

문제 링크

• 표가 2*N 형태로 있다.
• 첫째줄에는 1 ~ N이 순서대로 써있고, 두번째줄의 각 칸에는 1이상 N이하의 정수들이 랜덤하게 들어온다.
• 열을 여러개 뽑았을 때, 해당 열들의 첫째줄의 값들의 집합과 둘째줄의 값들의 집합이 일치하는 가장 많은 수의 열을 찾고, 해당 집합의 원소들을 출력하는 문제이다.

풀이 과정

• 그림에서 보면 공통점이 보인다.
• 결국, 첫째줄의 집합과 둘째줄의 집합이 같아야되고, 어떤 열의 첫번째 원소와 두번째 원소를 방향간선으로 이어주게 되면, 같은 집합이 되기위해서는 그래프에서 사이클이 생겨버린다.
• 사이클을 찾아주는 문제라는 파악까지 완료되면 N의 범위가 100이기 때문에 모든 원소에서 사이클이 존재하는지 안하는지를 판단하더라도 시간안에 들어오게 된다.
• 나는 사이클 문제라고 파악하고 나서 N의 범위를 적어뒀음에도 사이클에만 집착해서, dfs 트리에서 백엣지로 사이클 파악하는 방법으로 풀었다.

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

public class Main {
    static int N;
    static int[] arr;
    static int[] visit;
    static int cent, flag;
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(input.readLine());
        arr = new int[N + 1];
        visit = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(input.readLine());
        }
        for (int i = 1; i <= N; i++) {
            if (visit[i] == 0) {
                cent = 0;
                flag = 0;
                dfs(i);
            }
        }
        list.sort(((o1, o2) -> o1-o2));
        StringBuilder output = new StringBuilder();
        output.append(list.size()).append("\n");
        for (int num : list) {
            output.append(num).append("\n");
        }
        System.out.println(output);

    }

    static void dfs(int n) {
        visit[n] = 1;
        if (visit[arr[n]] == 0) {
            dfs(arr[n]);
        } else if (visit[arr[n]] == 1) {
            cent = arr[n];
            flag = 1;
        }
        visit[n] = 2;
        if (flag == 1) {
            if (cent != 0) {
                list.add(n);
                if (cent == n) {
                    flag = 0;
                }
            }
        }
    }
}