백준 10542 자바 - 마피아 게임 (BOJ 10542 JAVA)

문제 : https://www.acmicpc.net/problem/10542

 

  오랜만에 엄청 재밌는 문제였다. 그다지 복잡한 알고리즘적 지식을 요구하지 않으면서도 이렇게 난이도도 어느정도 있으면서 재밌게 낸것도 모자라서, 심지어 예제 입력들도 풀이를 생각하기 편하게 잘 내줬다. 출제자 멋져

 

  AD-HOC 문제로, 딱 이거다! 하는 해법 없이 논리적으로 맞다고 생각하는 방식들을 찾아 적용하며 풀어야 하는 문제이다. 일단 풀이과정은 한가지 확실한 조건(이하 '1'이 이에 해당함)에서 시작하면 판정을 위한 다른 방식들로 생각을 이어갈 수 있다.

 

 

1.

  문제에서 제시된 '마피아끼리는 서로 누군지 아는 상황이기 때문에 서로 지목을 안 하려고 할 것이다.'에 따라, 일단 맨 처음에 들어온 입력에서 한 번이라도 지목을 당했다면 마피아가 아니라고 볼 수 있다. 반대로 한 번도 지목을 안당했다면 마피아라고 봐도 된다!

 

우선 예제 1을 보자. 그래프로 그려보면 아래와 같다. 

이 경우, '마피아끼리는 서로 누군지 아는 상황이기 때문에 서로 지목을 안 하려고 할 것이다.'에 따라 1번은 일단 시민이라고 확정지을 수 있고, 3번은 아무에게도 지목을 당하지 않았으므로 사실 마피아인지 시민인지 모르지만, 이 문제는 '마피아가 최대한 몇 명이나 있는지'를 묻는 문제이므로 모르면 마피아라고 보면 된다! 따라서 3번은 마피아 확정이다.

 

마피아는 빨간색, 시민은 지워진(?) 녹색으로 그려본다면 아래와 같이 그릴 수 있다.

그럼 이제 2번은 어떻게 처리해야할까? 우선 확정된 애들은 더이상 생각하지 않아도 되므로 제외하고 보면 아래와 같이 혼자 남는다.

그럼 마찬가지로 2번을 특정할 수 있는 아무런 정보가 없으므로, 그냥 마피아라고 판단하면 된다. 따라서 예제 입력 1의 경우 마피아는 최대 2명이 있을 수 있다.

 

 

2.

  그럼 다른 조건을 찾아보자. 위에서 '예제 입력들도 풀이를 생각하기 편하게 잘 내줬다.'는게, 예제 입력 2에서 바로 보인다. 예제 입력 2를 그려보면 다음과 같다.

이 경우 시작부터 모두가 지목당한 상태(사이클이 생긴 상태)이다. 그럼 '1'의 논리를 적용시킬 수 없다. 이 경우는 뭘까? '마피아로 지목된 사람은 아무것도 모르는 척, 마피아가 아닌 척을 한다.'에 해당하는 사항으로 생각할 수 있다. 이 경우 간단하게 생각해보면 아무나 한명만 마피아라고 생각하면 된다...

 

라고 생각했다가 좀 많이 틀렸다 ㅋㅋ

이 경우 생각을 바꿔서 아무나 한명을 그냥 제거해서 사이클을 제거하고 다시 생각해보는게 맞다. 바꿔 말하면 아무나 한명이 마피아인게 아니고, 아무나 한명을 시민으로 생각하면 된다(마피아를 확정지을 수 없으니 '최대치의 마피아'를 만들기 위해 한명을 시민으로 생각해서 사이클을 없애는 것이다). 이 때 셋중 아무나 제거해도 된다. 그럼 '1'을 제거한다면 아래와 같다.

따라서 '2'를 마피아라고 보면 되는 것이다. 왜그렇냐면, 계속 2명, 3명 사이의 사이클만 확인해봐서 그렇게 됬는데 4명 이상의 사이클을 생각해보면 위와 같이 진행한 이유를 알 수 있다. 5명의 사이클을 그려보면 아래와 같다.

위와 같은 경우 1명만 마피아로 생각하면 마피아가 최대치가 될까? 아니다. 아래와 같이 1명을 빼서(아래에선 5번을 제거했으나 아무나 제거해도 됨) 사이클을 제거하고 2명을 마피아로 지정해야 한다. 

 

3.

  그럼 이걸 어떻게 구현해야 할까? DFS 같은걸로 계속 타고 들어가면서 연산하는 방법도 있겠지만, 내 경우에는 구현을 쉽게 하기 위해, 매 단계마다 '1'과 '2'를 적용하며 더이상 남은 인원이 없을 때 까지 계속 한 단계씩만 진행했다. 또한, 이미 확정된 부분에 대해서는 아예 생각하지 않고 재귀적으로(코드는 재귀가 아니다) 진행했다. 전체적인 과정을 보여주기 위해 예제 입력 3을 살짝 수정한 다음의 그래프를 보자.

 

3.1 입력을 받아 그래프를 표현한다. 설명을 위해 사용할 그래프는 다음과 같다. 

 

3.2 마피아를 확정한다.

 

3.3 위에서 선택된 마피아를 기준으로 한번만 움직여서 시민을 확정한다.

 

3.4 확정된 애들을 전부 지운다. (이와 같이 지우고 남은 노드가 solve함수 내의 remain 이다.) 참고로 '4->5'에서 4가 5를 가르켰으므로 마피아가 될 수 없다고 생각될 수 있는데, 시민이 가리킨건 이 문제에서 의미가 없는거라 아예 생각 안해도 된다!

 

3.5 다시 처음부터 과정을 진행한다. 우선 마피아를 확정하려고 보는데 이번엔 '설명2'의 경우이다. 따라서 아무거나 하나를 제거한다.

 

3.6 '설명1'에 따라 마피아를 확정한다.

 

3.7 다시 시민을 확정한다.

 

3.8 확정된걸 지운다.

3.9 마피아를 확정한다.

3.10 이제 확정되지 않은게 아무것도 없으므로 끝이다! 중간중간 확정된 마피아의 숫자만 잘 세주면 된다.

 

 

4.

  여기서 끝났으면 좋겠지만, 플래 티어 문제 답게 하나 더 남았다. 이건 각자 코드를 짠 방식에 따라 사실 신경쓰지 않아도 될 수 있다(정확히 말하자면 '설명2'와 같은 경우를 찾기 위해 DFS 등을 통해 사이클 판정을 하면 '4'의 과정이 필요 없다. 내 경우엔 카운팅해서 현재 남은 정점의 수와 카운팅이 같다면 사이클로 판정했으므로(코드의 'cnt == remain.size()' 부분), 서로 떨어진 그래프를 따로 생각하기 위해 '4'를 추가로 넣었다.

 

아래와 같은 경우를 보자.

이 경우 3개의 큰 그룹으로 나눠볼 수 있다(disjoint set). 따라서 각 연관된 그룹을 나누고, 별도로 돌렸다. 위와 같은 경우라면 '설명3'의 과정이 총 3번 돌아가게 된다. 코드의 아래 부분이 해당 역할을 한다.

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);

 

disjoint set을 만드는데는 union-find를 사용했다(코드의 initDisjointSet(), find(), union()).

 

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/10500/BOJ_10542.java

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

public 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++];
    }
}