백준 1154번 [팀 편성](C++) -yes6686- 티스토리

백준 문제 풀이: 1154 [팀 편성]

---

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

문제 설명:

n명의 사람들이 있으며, 일부 사람들끼리는 서로 적대적인 관계입니다. 모든 적대 관계를 고려하여 두 팀으로 나누되, 같은 팀에 속한 사람들끼리는 적대 관계가 없도록 합니다. 가능한 경우, 두 팀의 멤버를 출력하며, 불가능한 경우 -1을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> v[1001];

int checkA[1001];
int checkB[1001];
int ch[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    while (true) {
        int a, b;
        cin >> a >> b;
        if (a == -1 && b == -1) break;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    checkA[1] = 1;
    int count = 2;
    while (count--) {
        for (int i = 1; i <= n; i++) {

            for (int j = 0; j < v[i].size(); j++) {
                int k = v[i][j];

                ch[k] = 1;
            }
            ch[i] = 1;
            if (checkA[i] == 1) {
                for (int j = 1; j <= n; j++) {
                    if (ch[j] == 0) {

                        if (checkA[j] == 1) {
                            cout << -1 << '\n';
                            return 0;
                        }
                        checkB[j] = 1;
                    }
                }

            } else if (checkB[i] == 1) {
                for (int j = 1; j <= n; j++) {
                    if (ch[j] == 0) {

                        if (checkB[j] == 1) {
                            cout << -1 << '\n';
                            return 0;
                        }
                        checkA[j] = 1;
                    }
                }
            } else {

                int chA = 0;
                int chB = 0;

                for (int j = 1; j <= n; j++) {
                    if (ch[j] == 0) {

                        if (checkB[j] == 1) {
                            if (chA == 1) {
                                cout << -1 << '\n';
                                return 0;
                            }
                            chB = 1;
                        } else if (checkA[j] == 1) {
                            if (chB == 1) {
                                cout << -1 << '\n';
                                return 0;
                            }
                            chA = 1;

                        }
                    }
                }
                if (chB == 1) {
                    checkA[i] = 1;
                } else if (chA == 1) {
                    checkB[i] = 1;
                }

                if (count == 0) {
                    if (chB == 0 && chA == 0) {
                        checkA[i] = 1;
                    }
                }
                for (int j = 1; j <= n; j++) {
                    if (ch[j] == 1) continue;
                    if (chB == 1) {
                        checkB[j] = 1;
                    } else if (chA == 1) {
                        checkA[j] = 1;
                    }
                }

            }
            memset(ch, 0, sizeof(ch));

        }
    }
    cout << 1 << '\n';
    for (int i = 1; i <= n; i++) {
        if (checkA[i] == 1) {
            cout << i << " ";
        }
    }

    cout << -1 << '\n';
    for (int i = 1; i <= n; i++) {
        if (checkB[i] == 1) {
            cout << i << " ";
        }
    }
    cout << -1 << '\n';

}

예제

입력:
5
1 2
2 3
3 4
4 5
-1 -1

출력:
-1

---

코드 설명

• 적대 관계 저장: 그래프 형태로 적대 관계를 저장합니다.
• 팀 나누기: DFS와 조건 체크를 통해 두 팀으로 나누는 과정을 수행합니다.
• 충돌 감지: 팀을 나누는 과정에서 불가능한 상황이 발생하면 -1을 출력합니다.

시간 복잡도

• 팀 나누기: O(n^2) (n은 사람 수)
• 전체: 그래프의 크기와 사람 수에 비례

---

결과

코드는 주어진 조건에 따라 두 팀을 정확히 나누거나, 불가능한 경우를 탐지합니다. 추가적인 최적화나 개선 사항은 환영합니다!