[C/C++] 백준 #2252 줄 세우기(위상 정렬)

#2252 문제는 위상 정렬을 이용해서 풀 수 있는 문제입니다.

 

문제의 링크입니다.

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

2252번: 줄 세우기

위상 정렬은 작업의 선후관계 등에서 많이 사용됩니다.  소프트웨어 공학에서는 작업의 전체 시간을 결정하는 요소로도 많이 사용됩니다.  대부분의 경우 작업의 종류가 많지 않기 때문에 손쉽게 수작업으로도 표시할 수 있습니다.

 

위상 정렬과 관련된 문제들이 많이 있었으니, 참조하시길 바랍니다.

https://sdev.tistory.com/1119

[C/C++] 백준 #2056 작업(위상정렬)

https://sdev.tistory.com/894

[C/C++] 백준 #1766 문제집(위상정렬)

https://sdev.tistory.com/682

#1516 게임 개발

https://sdev.tistory.com/262

[C/C++] 백준 #1005 ACM Craft(위상 정렬)

 

줄 세우기 문제는 모두의 키에 대한 자료는 없지만, 일부의 학생들간에 누가 더 키가 큰지에 대한 정보를 가지고, 그 정보에 위배되지 않게 줄세우기 하는 방법입니다.  기타 다른 조건이 없이 여러가지 방법 중 하나만 제시하면 됩니다.

 

queue up

위상 정렬 알고리즘에 대한 자세한 설명은 이전 게시글을 참고바랍니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2252
//        - by Aubrey Choi
//        - created at 2019-09-28
//------------------------------------------------
#include <stdio.h>
#include <algorithm>
#include <queue>

int main()
{
    int n, m, f, t;
    static int v[32000], e[100000];
    std::queue<int> q;
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++) { scanf("%d%d",&f,&t); e[i]=(f-1)<<16|(t-1); v[t-1]++; }
    for(int i=0;i<n;i++) { if(!v[i]) q.push(i); }
    std::sort(e,e+m);
    while(!q.empty())
    {
        f=q.front(); q.pop();
        printf("%d ", f+1);
        auto it=std::lower_bound(e,e+m,f<<16);
        for(int i=std::distance(e,it);i<m;i++)
        {
            if((e[i]>>16)!=f) break;
            t=e[i]&0xffff;
            if(--v[t]==0) q.push(t);
        }
    }
    putchar('\n');
}