백준 02252 - 줄 세우기

출처 : https://www.acmicpc.net/problem/2252 

2252번: 줄 세우기

 

고려사항

• 위상정렬 알고리즘 사용.
• 위상정렬 설명이나 질문 페이지에 가면,
  자신에게 들어오는 간선의 수가 0인 정점이 더이상 없지만, 아직 방문 안한 정덤들이 있어
  더 이상 위상정렬을 진행할 수 없을 때, 이를 순환상태로 보고 이를 찾기 위해 그래프를 dfs로 탐색하는 방식이 있는데,
  굳이 왜그래야 하나 싶어서 내 생각대로 풀어보았다.
• edgeIn 벡터에 자신에게 들어오는 간선의 수를 기록하고, 그 값이 0이 될 때마다 zeroList에 넣어주어,
  다음 topology 큐에 들어갈 정점을 제로리스트 큐에서 가져오면 된다고 생각했고,
  제로리스트가 비었지만, 토폴로지 큐에 아직 안 들어간 정점들이 남아 있으면 이를 순환 상태로 보았고,
  이는 더 이상 정렬을 진행할 수 없는 상황이라 인덱스가 낮은 정점 부터 정답 큐에 넣고 뽑았다.
• 최종적으로는 정답 처리가 되었지만, 반례 데이터들도 잘 찾을 수 없고,
  테스트 케이스가 채점 시에 많이 없는 것 같은 느낌이 들어 로직적으로 정답인지는 모르겠다.
• 다른 위상정렬 문제들을 이 로직으로 풀 수 있는지 시도해보고,
  dfs나 스택을 사용하는 정석인 위상 정렬 알고리즘도 공부해 놔야 겠다.

 

#include <iostream>
#include <vector>;
#include <queue>
using namespace std;
 
bool visit[32001];
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int n, m, a, b, cur;
    cin>>n>>m;
 
    queue<int> topology, ans;
    priority_queue<int, vector<int>, greater<int>> zeroList;
    vector<int> edgeIn(n+1, 0);
    vector<vector<int>> edge(n+1);
 
    for(int i=0;i<m;++i){
        cin>>a>>b;
        edge[a].push_back(b);
        ++edgeIn[b];
    }
 
    for(int i=1;i<=n;++i){
        if(edgeIn[i] == 0){
            zeroList.push(i);
        }
    }
 
    if(!zeroList.empty()){
        topology.push(zeroList.top());
        zeroList.pop();
    }
 
    while(!topology.empty()){
        cur = topology.front();
        topology.pop();
        ans.push(cur);
        visit[cur] = true;
 
        for(int i : edge[cur]){
            --edgeIn[i];
            if(edgeIn[i] == 0){
                zeroList.push(i);
            }
        }
 
        if(!zeroList.empty()){
            topology.push(zeroList.top());
            zeroList.pop();
        }
    }
 
    for(int i=1;i<=n;++i){
        if(!visit[i]){
            ans.push(i);
        }
    }
 
    while(!ans.empty()){
        cout<<ans.front()<<" ";
        ans.pop();
    }
 
    return 0;
}