cdjs의 코딩 공부방

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

1. 문제

- $N$명의 사람들이 마피아 게임을 진행한다.

- 각 사람들이 마피아일것 같은 사람을 투표하게 되는데, 시민은 자신을 제외한 다른 사람 아무나 투표하고, 마피아는 시민 중 한 명에게 투표한다.

- 마피아일 수 있는 사람 수의 최대값을 출력하라.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

3-1. 문제 관찰 과정

문제를 처음 봤을 때, 솔직히 조금 어지러웠다. 문제 지문이 살짝 이해하기 힘든 점도 있기는 했지만, 그보다도 대체 문제 풀이를 어떻게 시작해야 할지 감도 안잡혔기 때문이다.

조금 생각하다 보니, 참가자의 투표를 유향 그래프로 나타내어 그래프를 직접 그려보면 문제 상황 자체를 쉽게 이해할 수 있다 생각이 들어 그림판을 켜서 예제 입력을 직접 그리며 관찰해 보았다.

"마피아는 서로 마피아를 투표하지 않는다" 라는 것은, 그래프가 a->b로 연결되어 있을 때 a번 사람이 마피아라면 b번 사람은 마피아일 수 없다는 것을 의미한다.

그런데, 어차피 a->b로 연결되어 a번 사람과 b번 사람이 동시에 마피아가 될 수 없다면 그래프를 유향 그래프로 그리는 것이 오히려 불편해지기 때문에, 무향 그래프로 바꾸어 생각해 보았다.

이렇게 무향 그래프로 바꾸고 나면 "서로 이웃하지 않는 노드들을 최대한 많이 선택할 때, 그 노드들의 개수를 구하여라" 라고 문제를 변환하여 생각할 수 있다.

처음에는 DP 문제일까 하고 고민해 보았는데, 어떻게 구현해도 시간 안에 예쁘게 구현될 것 같지 않아서 때려쳤다.

그렇게 계속 관찰하다가, "일단 반드시 골랐을 때 이득인 노드가 있을까?" 라는 생각으로 그래프를 살펴보았다.

가장 처음에는 연결된 개수가 가장 작은 것을 먼저 고르면 되는 그리디 문제인가 고민해 보았지만, 바로 반례를 찾아 폐기되었다.

그런데 반례를 만들다가 a->b->c로 일직선으로 (즉, 옆으로 새는 길 없이) 연결된 형태이며 a, b번 노드가 둘 다 단말 노드라면 b보다는 a를 고르는 것이 최적이라는 사실을 발견했다.

이를 조금 더 확장하여 문제를 해결해 보자.

3-2. 문제 풀이

각 정점을 사람의 번호, 간선은 서로가 투표했는지 여부에 따라 무향 그래프를 하나 생성한다.

그렇다면 문제가 "서로 이웃하지 않는 노드들을 최대한 많이 선택할 때, 그 노드들의 개수를 구하여라" 로 치환된다.

이 때, 반드시 단말 노드를 가장 먼저 고르는 것이 최적이라는 사실을 관찰을 통해 짐작할 수 있다.

이유는 간단한데, 단말 노드의 경우 간선이 단 하나만 연결되어 있으므로 해당 노드를 골랐을 때 고르지 못하게 되는 노드는 단 하나만 생긴다.

그런데 단말 노드 대신 고르지 못하게 되는 다른 노드를 고르게 되면 반드시 단말 노드를 고른 것보다 고를 수 있는 노드 수가 항상 같거나 적으므로, 단말 노드를 고르는 것이 더 최적해라는 것을 알 수 있다.

또한, 단말 노드가 존재하지 않을 때까지 노드를 고르면 나머지 그래프들은 전부 거대한 사이클 하나로 이루어진 그래프가 되는데, 사이클 하나로 이루어진 그래프에서는 반드시 (노드 개수 / 2) 만큼의 노드를 고를 수 있으니 각 사이클을 DFS로 돌며 크기를 확인하고 값을 더해주면 된다.

주의할 점은, 이 문제의 경우 그래프 하나가 아니라 끊어져 있는 서로 다른 여러 그래프가 나올 수 있으므로 사이클 크기 처리를 해 줄때 각 그래프에 대해 한 번씩 전부 돌며 연산해주어야 한다.

4. 코드

너무 신난 상태로 코드를 짜서 그런지 코드가 많이 더럽다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> visited;
vector<vector<int>> v;

int dfs(int node, int x) {
    visited[node] = 1;
    for (int i=0; i<v[node].size(); i++) {
        if (visited[v[node][i]])    continue;
        return dfs(v[node][i], x+1);
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    int n;
    int a[500005];
    int cnt[500005];
    int ans = 0;
    memset(cnt, 0, sizeof(cnt));
    cin >> n;
    
    v = vector<vector<int>>(n+1);
    visited = vector<int>(n+1, 0);
    
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        if (a[i] < i && a[a[i]] == i) {	// 서로가 서로를 지목한 경우;
            continue;
        }
        v[i].push_back(a[i]);
        v[a[i]].push_back(i);
        cnt[a[i]]++;	// 연결된 간선 개수
        cnt[i]++;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i=1; i<=n; i++) {
        pq.push({cnt[i], i});
    }
    
    while (!pq.empty()) {
        int sz = pq.top().first;
        int node = pq.top().second;
        pq.pop();
        if (visited[node])  continue;
        if (sz>1)  break;
        
        ans++;
        visited[node] = 1;
        for (int i=0; i<v[node].size(); i++) {
            int nnode = v[node][i];
            if (visited[nnode]) continue;
            visited[nnode] = 1;
            for (int j=0; j<v[nnode].size(); j++) {
                if (visited[v[nnode][j]])   continue;
                cnt[v[nnode][j]]--;
                pq.push({cnt[v[nnode][j]], v[nnode][j]});
            }
        }
    }
    
    for (int i=0; i<n; i++) {
        if (visited[i]) continue;
        ans += dfs(i, 1) / 2;
    }
    
    cout << ans;
}

5. 여담

오랜만에 정말 마음에 드는 문제를 풀었다. 관찰 과정부터 풀이 구현까지 전부 즐겁게 해결한 문제.

태그 중에 분리 집합이 있는 것을 보아하니 분리 집합으로도 풀 수 있는 모양이다.