취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7352번 문제인 Sorting it All Out이다.
문제는 아래 링크를 확인하자.

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

각 수를 정점으로, 대소관계를 방향에지로 모델링하면, 주어진 그래프가 문제의 조건을 만족하는 시점은 그래프가 (1) DAG이고 (2) 최장거리가 \(n\)이 되는 경우이며, 중간에 탐색이 끝나는 시점은 (1) 앞선 조건을 만족하는 순간이 오거나 (2) DAG가 아니게 되는 경우이다.

DAG 여부를 알아내는 것은 주어진 그래프에 사이클이 있는지 판정하는 것으로 할 수 있다. 또한 DAG의 최장거리는 위상정렬순으로 정점을 탐색하는 것으로 구할 수 있다. 이 두 알고리즘을 잘 구현하여 문제를 해결하자. 주어질 수 있는 노드의 수가 매우 적으므로, 매 탐색단계마다 위 과정을 매번 수행하는 것으로도 문제를 충분히 해결할 수 있다.

한 테스트케이스의 과정 중간에서 DAG가 아니게 되었다는 정보를 알아냈어도 그 테스트케이스에서 주어지는 모든 대소관계를 읽을 필요가 있다는 점에 유의하자.

아래는 제출한 소스코드이다.

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

int N, M;
vector<char> G[128];
pair<char, char> E[1000];

char par[128], lst;
int indeg[128], dist[128];
queue<int> que;

void func() {
    lst = 0;
    memset(par, 0, sizeof(par));
    memset(indeg, 0, sizeof(indeg));
    for (int i = 0; i < N; i++) {
        char x = 'A' + i;
        for (auto &y:G[x]) indeg[y]++;
    }
    memset(dist, 0, sizeof(dist));
    for (int i = 0; i < N; i++) {
        char x = 'A' + i;
        if (!indeg[x]) dist[x] = 1, que.push(x);
    }
    while (!que.empty()) {
        char cur = que.front(); que.pop();
        lst = cur;
        for (auto &nxt:G[cur]) {
            indeg[nxt]--;
            if (!indeg[nxt]) dist[nxt] = dist[cur] + 1, par[nxt] = cur, que.push(nxt);
        }
    }
}

void solve() {
    for (int m = 0; m < M; m++) {
        cin >> E[m].first >> E[m].second >> E[m].second;
    }
    for (char c = 'A'; c <= 'Z'; c++) G[c].clear();
    for (int k = 0; k < M; k++) {
        G[E[k].first].emplace_back(E[k].second);
        func();
        if (dist[lst] == N) {
            cout << "Sorted sequence determined after " << k + 1 << " relations: ";
            string ans = "";
            while (lst) {
                ans += lst;
                lst = par[lst];
            }
            while (!ans.empty()) {
                cout << ans.back();
                ans.pop_back();
            }
            cout << ".\n";
            return;
        }
        for (int i = 0; i < N; i++) {
            char x = 'A' + i;
            if (indeg[x]) {
                cout << "Inconsistency found after " << k + 1 << " relations.\n";
                return;
            }
        }
    }
    cout << "Sorted sequence cannot be determined.\n";
}

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

    cin >> N >> M;
    while (N) {
        solve();
        cin >> N >> M;
    }
}