[ 백준 2252 ] 줄 세우기 (C++)

백준의 줄 세우기(2252) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

학생들을 줄을 세워야 하는데, 전체 학생들의 키를 비교한 것이 아닌, 일부 학생들이 키를 비교한 것만으로 줄을 세워야

하는 문제이다.

본인은 이 문제를 '위상정렬'을 하는 방식으로 접근해보았는데, 위상정렬에 대해서 따로 포스팅한 글이 없으므로 간단하게

위상정렬이 무엇인지에 대해서 부터 알아보자.

위상정렬은 간단하게 생각해서 "일의 순서를 정하는 정렬" 이다.

우선순위가 정해져있는 여러 사건들 중에서, 가장 우선적으로 처리해야할 사건, 그 다음으로 처리해야할 사건들 이런

순서들로 일의 순서를 정하는 것이다.

이 문제도 마찬가지이다. 키 순서대로 줄을 세워야 하는데, 일부 학생들만 비교를 했다. 즉, 전체 학생들의 키를 순서대로는

알 수 없지만, "어떤 학생이 어떤학생보다 앞에오는지" 정도는 알 수 있다.

이러한 점에서 이 문제를 위상정렬로 구현했다.

구체적인 구현에 들어가기에 앞서 한 가지만 더 알아보자.

위상 정렬을 구현할 때, 특정 사건을 어느 시점에 처리해줘야 할까 ??

이 문제의 예제입력1을 예로 생각해보자.

예제입력1은 "1번 학생은 3번 학생보다 앞에 서야한다.", "2번 학생은 3번 학생보다 앞에 서야한다." 라는 2가지

조건만을 주고 3명의 학생을 줄을 세워야 한다.

그렇다면, 가장 우선적으로, 가장 처음으로 줄을 세워야 하는 학생은 몇번일까 ??

아마도 1번 혹은 2번일 것이다. 왜냐하면 3번 학생은, 1, 2번 학생이 모두 줄을 선 후에 줄을 설 수 있기 때문이다.

그래서 1번과 2번 중에서는 누가 먼저 서야할지 모르지만, 3번학생은 확실히 아니라는 것을 알 수 있다.

그럼 3번학생을 줄을 세워야 하는 타이밍은 언제일까 ??

바로 "1번 학생, 2번 학생이 모두 줄을 서고 난 후" 이다. 우리는 간단하게 이를 Count한 값으로만으로도 해결할

수 있다.

여기서 Count한다는 것은, "이 작업을 처리하기에 앞서, 우선적으로 처리해야 할 작업의 갯수" 를 의미한다.

즉, 3번학생의 Count값은 '2'일 것이다.

1번 학생의 Count값은 0일 것이고, 2번 학생의 Count 값 또한 0일 것이다.

특정 사건을 처리하기 위해서는 이 Count값이 0일 때 처리가 가능하다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, M;
int Entry[MAX];
vector<int> Node[MAX];
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Entry[b]++;
        Node[a].push_back(b);
    }
}
 
void Solution()
{
    queue<int> Q;
    for (int i = 1; i <= N; i++)
    {
        if (Entry[i] == 0) Q.push(i);
    }
    
    while (Q.empty() == 0)
    {
        int Cur = Q.front();
        Q.pop();
 
        cout << Cur << " ";
        for (int i = 0; i < Node[Cur].size(); i++)
        {
            int Next = Node[Cur][i];
            Entry[Next]--;
 
            if (Entry[Next] == 0) Q.push(Next);
        }
    }
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}