[BOJ 7352 // C++] Sorting it All Out

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

 

이번에 볼 문제는 백준 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;
    }
}