백준(BOJ)_줄 세우기(2252번)_C++

생각보다 쉽지 않은 문제...

처음부터 위상정렬을 떠올리긴 했으나 그냥 deque으로 구현했는데

시간초과가 나왔다.

그리고나서 삽질을 엄청하다가 결국 다른 분들의 도움을 받고야 마는데...

 

중요한 개념은 '나보다 앞에 설 사람이 없을 때 줄을 서는 것'!!

나는 무조건 입력이 들어오는대로 다 세우고 중간마다 위치를 바꿨는데

그냥 설 차례가 되면 서면 되는 것이었다!!

 

입력을 받으면서 나보다 앞에 서는 사람들의 수를 cnt 배열에 저장하고,

나보다 뒤에 서는 사람들의 목록을 v 벡터에 저장한다.

 

그러면 나보다 앞에 서는 사람들의 수가 0인 사람들부터 큐에 집어넣고,

한 명씩 줄 세우면서 그 사람의 v 벡터를 참조한다.

참조할 때 뒤에 서는 사람들 중 앞에 서는 사람의 수가 0인 사람을 큐에 집어넣는다.

(어우 말로 설명하기 힘드네)

 

위상정렬의 개념을 알고 있다면 코드를 보고 이해하기가 더 편할 것이다.

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

using namespace std;

int n, m;
vector<int> v[32001]; //자신의 뒤에 있는 사람
int cnt[32001]; //자신보다 앞서는 사람의 수

void solve(){
    queue<int> q;
    for(int i=1; i<=n; i++)
        if(cnt[i]==0) q.push(i);
    
    while(!q.empty()){
        int cur=q.front();
        q.pop();

        cout << cur << " ";

        for(int i=0; i<v[cur].size(); i++){
            int next=v[cur][i];
            cnt[next]--;

            if(cnt[next]==0) q.push(next);
        }
    }
}

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

    cin >> n >> m;
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        cnt[b]++;
        v[a].push_back(b);
    }

    solve();
}