백준 13344번: Chess Tournament (C++)

접근

https://www.acmicpc.net/problem/13344

13344번: Chess Tournament

체스 게임의 결과들이 M개 주어졌을 때, 이 게임들이 이루어질 수 있는 경우인지 아닌지를 정하는 문제이다. 즉, 같은 순위의 선수들끼리 순위를 정해주는 입력이 주어지거나, 선수들 순위들 사이에 엇갈리는 상하 관계가 주어질 때 inconsistent 를 출력해주면 된다.

이를 해결하기 위해 두가지 알고리즘을 이용할 수 있다.

1. 같은 순위의 선수들을 서로 연결하기 위한 Disjoint Set(Union Find) 알고리즘: 유니언 파인드 알고리즘을 이용하여 같은 순위에 있는 모든 선수들을 대표 선수 (부모 노드) 하나로 통합하여 계산을 쉽게 할 수 있다.
2. 선수들 사이의 상하 관계에 엇갈림이 없는지 확인하기 위한 위상 정렬(TopologySort): 위상 정렬은 보통 선후관계가 있는 일들의 순서를 정하기 위해 쓰이는데, 동시에 그래프에 사이클이 있는지 체크할 수 있다. 이 문제에서 사이클이 존재한다는 것은 하위권 선수가 다시 상위권 선수를 이긴다는 입력이 주어졌다는 뜻이므로 체스 토너먼트 결과의 결점을 확인하는 방법이 될 수 있다.

먼저 주어진 "=" 입력들을 먼저 처리하여 각 순위의 대표 선수 1명을 정하게 된다. 그리고 주어진 그래프들을 대표 선수로 전환하여 중복을 제거하고 새로 저장해준다. 그리고 이 남은 대표 선수들끼리의 위상정렬을 실행하여 이 선수들의 상하관계에 사이클이 있는지를 체크하여 경기 결과의 무결성을 확인한다.

코드

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 50001

int N, M;
int K, L;
char symbol;
int parent[MAX_N];
int inDegree[MAX_N];
vector<pair<int, int>> Graph;
set<int> GraphSet[MAX_N];
set<int> ParentsSet;

int Find(int x) {
    if (parent[x] == x) return x;
    return (parent[x] = Find(parent[x]));
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {
        parent[y] = x;
    }
}

int TopologySort() {
    queue<int> Q;
    for (int i : ParentsSet) {
        if (inDegree[i] == 0) Q.push(i);
    }
    for (int i = 0; i < ParentsSet.size(); i++) {
        if (Q.empty()) {
            return 0;
        }
        int x = Q.front();
        Q.pop();
        for (int j : GraphSet[x]) {
            if (--inDegree[j] == 0) {
                Q.push(j);
            }
        }
    }
    return 1;
}

int Solve() {
    // 위상 정렬을 위해 같은 순위의 선수들을 모두 같은 순위의 대표 선수(parent[x])로 교체하고 중복 그래프 제거
    for (pair<int, int> Temp : Graph) {
        int a = Find(Temp.first);
        int b = Find(Temp.second);
        // a == b 인 경우: 같은 순위끼리의 선수들 사이에 상하 입력이 주어진 경우 inconsistent
        if (a == b) return 0;
        ParentsSet.insert(a);
        ParentsSet.insert(b);
        if (!GraphSet[a].count(b)) {
            GraphSet[a].insert(b);
            inDegree[b]++;
        }
    }
    // 위상 정렬을 진행하여 정렬이 되면(그래프에 사이클이 없으면) consistent, 아니라면 inconsistent
    if (TopologySort()) {
        return 1;
    } else {
        return 0;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    // Disjoint Set 알고리즘을 위한 parent 배열 초기화
    for (int i = 0; i < N; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < M; i++) {
        cin >> K >> symbol >> L;
        if (symbol == '=') {
            // 입력된 두 선수가 동일한 실력일 경우 Union
            Union(K, L);
        } else {
            // 실력에 순서를 갖고 있을 경우 Graph 벡터에 저장
            Graph.push_back(make_pair(K, L));
        }
    }

    if (Solve()) {
        cout << "consistent" << endl;
    } else {
        cout << "inconsistent" << endl;
    }
    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!