[C++ 백준 풀이][Gold] 2252번 : 줄 세우기 / 1766번 : 문제집 (위상 정렬)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 '2252번 : 줄 세우기'와 '1766번 : 문제집' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 두 문제 모두 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 위상 정렬의 개념에 대해 다룰 것입니다.

 

 

2252번 : 줄 세우기

 

N명의 학생들을 순서대로 배열할 때, 어떤 학생은 반드시 다른 학생의 앞에 배치되도록 할 때 해당 조건을 모두 만족하도록 학생을 배치하여 출력하는 문제입니다.

예를 들어 예제 입력 1의 경우 1은 3보다 앞에 와야하고 2는 3보다 앞에 와야 하므로 가능한 답은 1 2 3과 2 1 3이 있습니다.

답이 여러 가지인 경우 아무거나 출력할 수 있다고 했으므로 예제 출력이 주어진 것과 달라도 됨을 인지해야 합니다.

 

이 문제를 풀이하기 위해서는 위상 정렬의 개념에 대해 알아야 합니다. (사실 몰라도 풀 수는 있습니다.)

 

 

예를 들어 위와 같이 단방향 간선들로 연결된 그래프가 있을 때, 자신을 향해있는 노드가 없는 노드들부터 순차적으로 지워가면서 출력하는 알고리즘입니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있으니 참고해 주세요.

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

int degree[32005] = {0, };
vector<int> node[32005];
queue<int> Queue;

int main() {
    int N, M, A, B, pop;
    cin >> N >> M;
    for(int i=0; i<M; i++) {
        cin >> A >> B;
        node[A].push_back(B);
        degree[B]++;
    }
    for(int i=1; i<=N; i++)
        if(!degree[i]) Queue.push(i);
    while(!Queue.empty()) {
        pop = Queue.front();
        Queue.pop();
        cout << pop << " ";
        for(int i=0; i<node[pop].size(); i++) {
            degree[node[pop][i]]--;
            if(!degree[node[pop][i]]) Queue.push(node[pop][i]);
        }
    }
}

 

 

위에서 언급한 위성 정렬 알고리즘을 구현하기 위해서는, 노드를 향하는 간선이 몇 개나 있는지 그 차수를 저장해야 합니다.

그래서 차수를 저장하는 degree 배열을 선언하여 연결된 간선의 수를 저장하였습니다.

그리고 vector로 node를 선언하여 A와 B가 입력되면 A 노드가 B로 연결되어 있음을 저장하였습니다.

이 경우 B 쪽으로 간선이 연결되어 있기 때문에 degree[B]를 1 증가시켜주어야 합니다.

 

노드들을 지워나갈 때는 degree가 0인 것부터 지워나가고, 노드를 지울 때마다 해당 노드가 가리키는 노드의 차수를 1 낮춰주면서 순차적으로 출력해주면 됩니다.

 

 

풀이 코드를 제출해보면 84ms 정도의 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.

 

 

1766번 : 문제집

 

이 문제 역시 위상 정렬을 활용하는 문제에 해당하여 같이 가져와봤습니다.

문제가 길지만 정리해보면 문제의 쌍이 주어질 때, 앞에 오는 문제가 반드시 뒤의 오는 문제보다 먼저 풀도록 하여 문제 푸는 순서를 출력하는 것입니다.

이 때 조건이 하나 추가되어 있는데, 답이 여러 가지인 경우가 있을 수 없도록 조건이 달리 없다면 번호가 빠른 것을 먼저 풀도록 해야 합니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

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

int degree[32005] = {0, };
vector<int> node[32005];
priority_queue<int, vector<int>, greater<int>> Queue;

int main() {
    int N, M, A, B, pop;
    cin >> N >> M;
    for(int i=0; i<M; i++) {
        cin >> A >> B;
        node[A].push_back(B);
        degree[B]++;
    }
    for(int i=1; i<=N; i++)
        if(!degree[i]) Queue.push(i);
    while(!Queue.empty()) {
        pop = Queue.top();
        Queue.pop();
        cout << pop << " ";
        for(int i=0; i<node[pop].size(); i++) {
            degree[node[pop][i]]--;
            if(!degree[node[pop][i]]) Queue.push(node[pop][i]);
        }
    }
}

 

풀이는 위의 문제와 아주 비슷한데, 큐 대신 우선순위 큐를 선언하여 중요도가 비교되지 않으면 번호가 작은 것이 먼저 출력될 수 있도록 greater<int> 조건을 추가해줍니다.

이후 degree가 0인 원소들 중에서 pop할 때 top의 원소를 출력하면 번호가 작은 것이 먼저 출력되게 됩니다.

 

 

풀이 코드를 제출해보면 같은 알고리즘이기 때문에 거의 같은 시간에 문제가 해결됨을 확인할 수 있습니다.

위상 정렬의 개념에 대해 잘 이해할 수 있는 문제였습니다.