[BOJ] #1953 팀배분

시간 제한	메모리 제한	정답 비율
2 초	128 MB	43.773%

 

1953번: 팀배분

 

문제

청팀과 백팀으로 두 팀을 나누어 팀전을 하려 한다. 하지만 서로 같은 팀을 하기 싫어하는 사람들이 생겼다.

이제 우리가 할 일은 다음과 같다. 사람들이 각각 싫어하는 사람들의 정보가 주어져 있을 때, 그 사람들의 요구를 수용하여 서로 싫어하는 사람은 같은 팀에 넣지 않으려 한다. 이 조건을 만족하여 n명의 사람들 두 팀으로 나누는 프로그램을 작성하여라.

스페셜 저지 문제로, 꼭 내가 푼 방법이 아니더라도 다양한 방법과 답이 존재한다.

 

해결

key point, 이웃된 노드를 흰색, 파란색으로 번갈아가면서 색칠한다.
               흰색은 1, 파란색은 -1로 보고 팀판별과 동시에 방문판단도 하기 위해서 chk배열에 저장했다.

1. i번 사람이 싫어하는 사람들의 정보가 주어지면, i는 그 사람들과 같은 팀이 되어선 안된다.
2. 따라서, 상대방이 i를 싫어하지 않아도, i번 사람이 싫어하는 사람들을 임의로 i_a, i_b ... 라고 나타내면,
   i와 i_a, i_b... 는 서로 싫어하는 관계로 지정했다. → 양방향 그래프
3. 1번은 무조건 흰팀(1)으로 보고 dfs를 시작하여 연결되어 있는 노드에 대해서 반대색깔(-1)로 칠한다.
4. 이렇게 모든 노드에 대해서 색깔이 다 칠해질때까지 반복문이 실행된다.
5. 그리고 다시 한 번 n만큼 반복문을 돌면서 1이라면 흰팀, -1이라면 파란팀에 분류하고
6. 각각의 팀의 인원수와 속한 사람들을 출력한다.

도움된 testcase

4
1 3
1 4
1 4
0

이 테스트케이스를 보고, 처음에는 단방향대로 모두 주어지니까 따로 양방향으로 처리안해줘도 되겠다 싶었다가
i는 i_a를 싫어하는데, i_a는 i를 싫어하지 않을 수도 있고, 싫어하는 사람이 그냥 없는 사람도 있을 수 있고..
그래서 모든 경우에 대해서 더 쉽게 처리하기 위해서 양방향으로 저장해놨다.

 

코드

메모리	시간
1988KB	0ms

#include <iostream>
#include <vector>
using namespace std;
int n, chk[105];
vector<int> white, blue, arr[105];
 
void dfs(int num, int team) {
    chk[num] = team;
    for (auto child : arr[num]) {
        if (chk[child])    continue;
        dfs(child, team * -1);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        for (int j = 0, b; j < a; j++) {
            scanf("%d", &b);
            arr[i].push_back(b);
            arr[b].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!chk[i]) {
            dfs(i, 1);
        }
    }
 
    // white 1, blue -1 나누기
    for (int i = 1; i <= n; i++) {
        if (chk[i] == 1) {
            white.push_back(i);
        }
        else {
            blue.push_back(i);
        }
    }
 
    vector<int>::iterator it;
    printf("%d\n", white.size());
    for (it = white.begin(); it != white.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n%d\n", blue.size());
    for (it = blue.begin(); it != blue.end(); it++) {
        printf("%d ", *it);
    }
 
    return 0;
}