(Elice / 그래프 / Java) 마피아는 몇 명?

마피아는 몇 명?

카드 병정들은 점심시간에 마피아 게임을 즐겨합니다. 마피아 게임이란 참가자의 일부는 마피아가 되고 나머지 참가자들은 시민이 되어 누가 마피아인지 알아내면 되는 게임입니다. 마피아들끼리는 서로 마피아임을 알고 있으며 정체를 들키지 않기 위해 연기를 해야 합니다.

게임이 진행되면서 현재 N명의 참가자가 살아있다고 합니다. 참가자들은 짐작을 통해 마피아를 지목하여 누가 마피아인지 밝혀내야 합니다. 또한 마피아끼리는 서로 마피아임을 알기 때문에 서로 지목하지 않는다고 합니다.

누가 마피아인지 모를 때, 이들 중 최대 몇 명의 마피아가 있을 수 있는지 구하는 프로그램을 작성하세요.

 

지시사항

입력

• 첫째 줄에는 현재 살아있는 카드 병정의 수를 나타내는 정수 N을 입력합니다
• 참가자들은 1에서 N까지의 수를 차례대로 등에 붙입니다.

                                                          (2<N<1,000)

• 다음 N개의 줄을 입력하며 2번째 줄을 기준으로 K 번째 입력된 줄은 등 번호가 K 번인 참가자가 지목한 등 번호입니다.
• 자기 자신은 지목할 수 없습니다.

출력

• 이 게임에서 가능한 마피아의 최대 인원을 출력합니다.

입력 예시

3
2
1
1

출력 예시

2

예제에서 마피아로 의심되는 사람은 2번, 3번입니다.

 

소스코드

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;

 class Main extends FastInput {
    private int solve(int n, int[] choice, ArrayList<Integer> remain) {
        int answer = 0;
        int[] state = new int[n+1];
        Queue<Integer> q = new ArrayDeque<>();

        while (remain.size() != 0) {
            boolean[] isCitizen = new boolean[n+1];
            int cnt = 0;
            for (int i = 0; i < remain.size(); i++) {
                int num = remain.get(i);
                int to = choice[num];
                if (!isCitizen[to] && state[to] == 0) {
                    cnt++;
                    isCitizen[to] = true;
                }
            }

            if (cnt == remain.size()) {
                state[remain.get(0)] = 1;
                ArrayList<Integer> remainTmp = new ArrayList<>();
                for (int i = 0; i < remain.size(); i++) {
                    int num = remain.get(i);
                    if (state[num] == 0) {
                        remainTmp.add(num);
                    }
                }
                remain = remainTmp;
                continue;
            }

            for (int i = 0; i < remain.size(); i++) {
                int num = remain.get(i);
                if (!isCitizen[num]) {
                    state[num] = -1;
                    q.add(num);
                }
            }

            answer += q.size();

            while (!q.isEmpty()) {
                int to = choice[q.poll()];
                state[to] = 1;
            }

            ArrayList<Integer> remainTmp = new ArrayList<>();
            for (int i = 0; i < remain.size(); i++) {
                int num = remain.get(i);
                if (state[num] == 0) {
                    remainTmp.add(num);
                }
            }
            remain = remainTmp;
        }
        return answer;
    }

    private int[] parents;

    private int find(int a) {
        if (parents[a] < 0) return a;
        return parents[a] = find(parents[a]);
    }

    private void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;

        int h = parents[a]<parents[b] ? a:b;
        int l = parents[a]<parents[b] ? b:a;
        parents[h] += parents[l];
        parents[l] = h;
    }

    private void initDisjointSet(int n) {
        parents = new int[n+1];
        Arrays.fill(parents, -1);
    }


    private void solution() throws Exception {
        int n = nextInt();
        int[] choice = new int[n+1];
        initDisjointSet(n);

        for (int i = 1; i <= n; i++) {
            choice[i] = nextInt();
            union(i, choice[i]);
        }

        ArrayList<Integer>[] remain = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            int findNum = find(i);
            if (remain[findNum] == null)
                remain[findNum] = new ArrayList<>();
            remain[findNum].add(i);
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (remain[i] == null) continue;
            answer += solve(n, choice, remain[i]);
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}