[ 백준 1953 ] 팀배분 (C++)

백준의 팀배분(1953) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 서로 싫어하는 사람을 같은 팀으로 넣지 않고, 팀을 만드는 방법을 구현해야 하는 문제이다. 팀의 인원수는 반드시 똑같을

   필요는 없다.(A팀 : 1명 , B팀 : 9명 이런식으로)

   먼저 본인은 MAP[][] bool 형 2차원 배열을 이용해서 싫어하는 사람의 관계를 false로 표시해 주었다.

   이 때, 양방향으로 표현을 해도 무방하다. 사실, 문제에는 A가 B를 싫어하면 B도 A를 싫어한다 라는 가정이 없지만,

   A가 B를 싫어하면, 절대로 A와 B는 같은 팀이 될 수 없으므로, B도 A를 싫다고 표현해도 무방하다.

   또한 본인은 팀을 Visit[] 1차원 배열을 통해서 만들었다. Visit[] 배열의 값이 1인 팀과, -1인 팀으로 나누어 주었다.

   동시에, 탐색 체크를 위해서 Visit배열의 값이 0인 사람은 아직 방문하지 않았음을 의미하게 구현해 주었다.

2) 본인은 BFS를 이용해서 구현해주었다. 이미 방문하지 않은 점에 대해서 탐색을 하되, 싫어하는 사람이라면

   현재 사람의 Visit값의 -1을 곱하는 식으로 구현을 해 주었다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
#define MAX 101
using namespace std;
 
int N;
bool MAP[MAX][MAX];
int Visit[MAX];
 
void Input()
{
    memset(MAP, true, sizeof(MAP));
    memset(Visit, 0, sizeof(Visit));
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int a; cin >> a;
        for (int j = 0; j < a; j++)
        {
            int b; cin >> b;
            MAP[i][b] = false;
            MAP[b][i] = false;
        }
    }
}
 
void BFS()
{
    queue<int> Q;
    vector<int> A, B;
 
    for (int i = 1; i <= N; i++)
    {
        if (Visit[i] != 0) continue;
        Visit[i] = 1;
        Q.push(i);
 
        while (Q.empty() == 0)
        {
            int Cur = Q.front();
            Q.pop();
 
            for (int j = 1; j <= N; j++)
            {
                if (Visit[j] != 0) continue;
                if (MAP[Cur][j] == false)
                {
                    Visit[j] = Visit[Cur] * (-1);
                    Q.push(j);
                }
            }
        }
    }
 
    for (int i = 1; i <= N; i++)
    {
        if (Visit[i] == 1) A.push_back(i);
        else if (Visit[i] == -1) B.push_back(i);
    }
 
    cout << A.size() << endl;
    for (int i = 0; i < A.size(); i++) cout << A[i] << " ";
    cout << endl << B.size() << endl;
    for (int i = 0; i < B.size(); i++) cout << B[i] << " ";
    cout << endl;
}
 
void Solution()
{
    BFS();
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}