[BOJ 1889] 선물 교환 풀이 (C++)

문제

해당링크에서 문제를 확인하실 수 있습니다.

풀이

제 풀이의 주요 아이디어는 다음과 같습니다.

→ 선물 받은 개수가 2보다 작은 사람은 반드시 제외시켜야 한다.

만약, 선물 받은 개수가 2보다 작다면 어떠한 방법을 취해도 더 많은 선물을 받을 수 없습니다. 따라서 이러한 사람들은 반드시 제외시켜야 합니다. 이러한 사람을 i라고 해봅시다. 선물 교환에서 i를 제외시키면 i에게 선물받은 사람들은 받은 선물 개수가 줄어들게 됩니다. 이렇게 줄어든 선물 개수가 또다시 2보다 작다면, 이 사람 또한 제외시켜 주어야 합니다. 이를 반복해 확인해주면 됩니다.

코드를 통해 부가 설명을 드리겠습니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

int n;
int graph[200000]; // i에게 선물을 준 사람 수
pii arr[200000]; // i가 지목한 pair
int vis[200000]; // vis[i] = 1이면 i는 제외시켜야 한다.
queue<int> q;

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        graph[a]++; // i가 a를 투표함
        graph[b]++; // i가 b를 투표함
        arr[i] = {a, b};
    }
    for(int i = 0; i < n; i++) {
        if (graph[i] < 2) {
            vis[i] = 1;
            q.push(i);
        }
    }

    while(!q.empty()) {
        int t = q.front(); q.pop();

        if (--graph[arr[t].first] < 2 and !vis[arr[t].first]) {
            q.push(arr[t].first);
            vis[arr[t].first] = 1;
        }
        if (--graph[arr[t].second] < 2 and !vis[arr[t].second]) {
            q.push(arr[t].second);
            vis[arr[t].second] = 1;
        }
    }

    int cnt = 0;
    for(int i = 0; i < n; i++) {
        if (vis[i]) cnt++;
    }
    printf("%d\n", n - cnt);
    for(int i = 0; i < n; i++) {
        if (vis[i]) continue;
        printf("%d ", i + 1);
    }
}

graph[i]는 i에게 선물을 준 사람 수 입니다. 그래프 관점으로 봤을때 i의 inDgree라고도 볼 수 있습니다.
arr[i]는 i가 선물 준 두명의 사람을 pair로 저장합니다.
vis[i]는 i를 제외시켜야 하는지 여부를 나타냅니다.

위에서 언급했던 풀이를 while문 안에서 반복합니다. 제외당한 사람에게 선물을 받아graph[arr[t].first], graph[arr[t].second]값이 1 줄어들게 됩니다. 이 값이 2보다 작으면서 제외된 적이 없는 사람이면 queue에 넣어줍니다.

그리고 마지막에 제외된 사람을 cnt 변수에 저장하고 결과를 출력합니다.

한가지 주의할 점은, 방문 처리를 queue에 넣고난 후 해야한다는 것입니다. 이는 BFS 방문처리하는 것과 비슷한데, 만약 방문처리를 나중에 한다면 queue에 같은 값이 들어갈 수 있게 됩니다. 이렇게 될 경우 중복 계산이 발생해 정답과 다른 결과값이 나올 수 있습니다.

이렇게 하면 안된다는 겁니다.

	...
    for(int i = 0; i < n; i++) {
        if (graph[i] < 2) q.push(i);
    }
    while(!q.empty()) {
        int t = q.front(); q.pop();
        vis[t] = 1;
        if (--graph[arr[t].first] < 2 and !vis[arr[t].first]) q.push(arr[t].first);
        if (--graph[arr[t].second] < 2 and !vis[arr[t].second]) q.push(arr[t].second);
    }
	...

마치며

아이디어가 꽤 재밌는 문제였습니다. 난이도가 낮은 편이라 우습게 봤는데 방문 처리 때문에 좀 헤맸었네요..ㅜㅜ