[C++]백준 - 2252번 문제

2252번: 줄 세우기 (acmicpc.net)

2252번: 줄 세우기

 

2252번 : 줄 세우기

---

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

 

 

출력

---

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

 

---

 

생각해 볼 점

---

위상 정렬 문제입니다.

 

우선 Pre라는 배열을 하나 만들어서, 이 학생 앞에 몇 명이 있는 지 저장합니다.

 

그 외에는 그래프 처럼 방향 간선을 사용하여 학생들의 앞 뒤를 정해줍니다.

 

예를 들어, 1번 학생 뒤에 3번 학생이 와야 한다면,

 

1 -> 3 이라는 간선을 만들고, Pre[3]++ 를 수행하여

 

3번 학생 앞에 1명이 있으며, 1번 학생 뒤에는 3번 학생이어야 함을 명시합니다.

 

모든 작업이 끝났으면, Pre 배열을 순회하여 앞에 아무도 없는 Pre[i] = 0인 학생들만 큐에 집어넣고

 

그래프 순회를 시작하면 될 것입니다.

 

그래프 순회를 할 때에는 다음과 같이 수행합니다.

 

예를 들어, 1번 학생이 큐에 있으면,

 

1. 1번 학생을 큐에서 뽑는다.

2. 1번 학생 뒤에 있는 모든 학생들의 번호를 순회한다.

3. 순회한 학생 번호에 해당하는 번호가 i 일때, Pre[i]--를 수행한다.

4. Pre[i]--를 수행하여 Pre[i] == 0이 된 학생들을 모두 큐에 담는다.

 

코드

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() 
{
    int N, M;
    scanf("%d %d", &N, &M);
    
    vector<int> *order = new vector<int>[N];
    int *pre = new int[N];
    fill_n(pre, N, 0);
    for(int i = 0; i < M; i++)
    {
        int A, B;
        scanf("%d %d", &A, &B);
        A--; B--;
        
        order[A].push_back(B);
        pre[B]++;
    }
    
    queue<int> q;
    int count = N;
    while(count)
    {
        for(int i = 0; i < N; i++)
        {
            if(pre[i] == 0) 
            {
                q.push(i);
                pre[i]--;
            }
        }
        while(!q.empty())
        {
            int st = q.front();
            printf("%d ", st + 1);
            for(int next_st : order[st]) pre[next_st]--;
            count--;
            q.pop();
        }
    }
    
    delete[] order;
    delete[] pre;
	return 0;
}

 

그 외

---