[백준 1889번] 선물 교환 (C++)

문제링크 : https://www.acmicpc.net/problem/1889

1889번: 선물 교환

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, x, y;
int inDegree[200001];
int check[200001]; //방문체크

vector<pii>arr[200001]; //연결된 인원
vector<int>result; //참여 인원들

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
 
    for(int i=1; i<=N; i++)
    {
        cin >> x >> y;
        inDegree[x]++; //진입차수 증가
        inDegree[y]++;
        arr[i].push_back({x, y});
    }

    queue<int>q;
    for(int i=1; i<=N; i++)
    {
        if(inDegree[i] < 2) q.push(i); //참여 불가
    }

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

        if(check[cur]) continue; //중복탐색 방지
        check[cur]=1;

        for(int i=0; i<arr[cur].size(); i++)
        {
            auto[next1, next2] = arr[cur][i]; //인접한 페어 확인
            if(--inDegree[next1] < 2) q.push(next1);
            if(--inDegree[next2] < 2) q.push(next2);
        }
    }

    int cnt=0;
    for(int i=1; i<=N; i++)
    {
        if(inDegree[i]==2) //무사 참여
        {
            cnt++;
            result.push_back(i);
        }
    }

    cout << cnt << "\n";
    for(int i=0; i<result.size(); i++) cout << result[i] << " ";

    return 0;
}

 

위상정렬 알고리즘을 이용한 문제이다.

해당 문제에서는 참여못하는 인원의 조건인 받은 선물이 2개 미만인 인원을 큐에 넣고 시작한다.

 

해당 값을 기준으로 인접한 값들 (페어) 을 확인한다.

각각의 인접한 값에서 -1을 해주고 빼준 값이 2 미만이면 해당 값을 큐에 넣고 위 과정을 반복한다.

과정중에 큐에 들어온 값에 대해 방문처리를 하여 중복탐색을 방지하도록 해준다.

 

위 탐색을 마치고 각 인원이 가진 선물이 2개가 맞는지 확인을 해준다.

선물이 2개가 맞다면 무사히 참여를 완료한 것이기에 카운팅과 함께 해당 인원을 따로 배열에 저장해준다.

이렇게 저장한 카운팅과 해당 인원을 각각 출력해주면 된다.

 

해당 문제의 경우 i가 4에 해당하는 인원의 경우 받은 것이 없고, 3개씩 받은 인원에게 1개씩 나눠받아야 2개를 채우는 것이 가능하다.

따라서 해당 인원은 참여가 불가능하다.

이외의 인원들은 모두 2개 이상의 값을 가지고 있기에 정상적으로 참여가 가능하다.