[백준] 2252번 줄 세우기 C++ 코드

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n,m,inj[32004],x,y;
vector<int> adj[32004];
vector<int> v;
// 키는 순환이 생길 수 없음
// 순서가 있게 진행 -> 위상정렬

int main() {
    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
        inj[y]++;
    }

    queue<int> q;

    for(int i = 1; i < n + 1; i++) {
        if(inj[i] == 0) {
            q.push(i);
            v.push_back(i);
        }
    }

    while(!q.empty()) {
        int pn = q.front();
        q.pop();
        for(int i : adj[pn]) {
            inj[i]--;
            if(inj[i] == 0) {
                q.push(i);
	            // 키 순서는 단일 선행 작업 
                v.push_back(i);
            }
        }
    }

    for(int i = 0; i < v.size(); i++) {
        cout << v[i];
        if(i != n - 1) cout << " ";
    }
    cout << '\n';

    return 0;
}

풀이

키 순서 세우기 문제는 학생 간의 순서 관계를 기반으로, 정확한 순서대로 정렬하는 문제이다. 학생 간의 비교 관계는 다일 경로를 형성하므로, 각 학생의 선행 학생이 하나 뿐이다. 이는 선행 작업이 여러 개 있지 않기 때문에, 작업 완료 시간을 계속 갱신할 필요가 없다. 따라서 단순히 if(inj[i] == 0) 조건에서 선행 작업이 끝난 후에만 처리하면 된다. 선행 작업이 하나뿐이라면, 위상 정렬에서 큐에 넣고 하나씩 처리하는 방식으로 순서를 정확하게 세울 수 있다.

 

키 순서 문제는 절대적인 완료 시간이 아닌, 단순히 순서대로 나열할 수 있는지를 확인하는 문제로 선행 학생이 정렬되면 그 다음 학생을 바로 추가할 수 있다.