[BOJ] 숫자 고르기

문제

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다.
첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다.
이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다.
이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다.
그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

풀이

위 아래의 정수 집합이 일치해야 하는 문제이다.
그렇다면 정수 집합이 일치해야 하는 조건이 무엇일까?
일치 조건은 바로 순환이다.
두 조합이 일치하려면 걸국 순환해서 다시 돌아와야 한다.
따라서 순환하는 갯수를 더해주면 된다.

필자는 매 BFS 탐색마다 key와 value리스트에 각 key와 value를 담아서
두 조합이 일치하는 여부에 따라서 순환의 여부를 판단하였다.

import java.util.*;
import java.util.stream.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();
        boolean[] visited = new boolean[N + 1];

        for(int i = 1; i <= N; i++) {
            int num = Integer.parseInt(br.readLine());
            map.put(i, num);
        }

        List<Integer> maxList = new ArrayList<>();
        for(int i = 1; i <= N; i++) {
            Arrays.fill(visited, false);
            List<Integer> list = new ArrayList<>();
            int count = bfs(visited, i, map, list);
            if (2 <= count) {
                maxList.addAll(list);
            }
        }
        maxList = maxList.stream().distinct().collect(Collectors.toList());

        for (int a : map.keySet()) {
            if (a == map.get(a)) {
                maxList.add(a);
            }
        }

        System.out.println(maxList.size());

        Collections.sort(maxList);
        for(int a : maxList) {
            System.out.println(a);
        }


    }

    static int bfs(boolean[] visited, int start, Map<Integer, Integer> map, List<Integer> keyList) {
        int count = 1;
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> valueList = new ArrayList<>();
        keyList.add(start);
        queue.add(start);
        while(!queue.isEmpty()) {
            int n = queue.poll();
            int value = map.get(n);
            valueList.add(value);
            if (!visited[value]) {
                visited[value] = true;
                keyList.add(value);
                count++;
                queue.add(value);
            }
        }

        if (!valueList.containsAll(keyList)) {
            count = 0;
        }
        return count;
    }
}