[2252번] 줄 세우기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 위상 정렬(Topological Sort) :: http://www.crocus.co.kr/716

기본적인 위상 정렬 알고리즘을 이용한 문제이다.

위의 위상 정렬 개념 설명 및 개념에 해당하는 예제 코드를 올렸는데 그 코드에서 input 부분만 바꾸면 AC를 받는다.

이 문제에 대한 설명은 위의 주소에서 공부하고 익히도록 하자.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <iostream> #include <cstdio> #include <queue>   using namespace std;   vector<int> vc[32001]; int line[32001];   int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 0; i < m; i++)     {         int cur, prev;           // prev값에 cur을 넣어주고 cur의 간선추가를 확인해준다.         scanf("%d %d", &prev, &cur);           line[cur]++;         vc[prev].push_back(cur);     }       int result[32001];     queue<int> q;       for (int i = 1; i <= n; i++)         if (line[i] == 0)             q.push(i);       for (int i = 0; i < n; i++)     {         if (q.empty())         {             printf("0");             return 0;         }           int cur = q.front();         q.pop();           result[i] = cur;           for(int j = 0 ; j < vc[cur].size(); j++)         {             int next = vc[cur][j];             if (--line[next] == 0)                 q.push(next);         }              }         for (int i = 0; i < n; i++)             printf("%d ", result[i]);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus