[Beakjoon] 1766 문제집 (C++)

문제 링크

BOJ 1766: 문제집

문제

문제 자체는 이해하기 쉽지만, 위상정렬 알고리즘을 알지 못한다면 풀이법을 떠올리기 쉽지 않은 문제인 것 같다.

총 M개의 위치관계가 주어질 때 N개의 수를 해당 위치 관계를 모두 만족하면서 오름차순으로 정렬되도록 해야한다.

풀이

뭔가 알듯말듯 어디서 배워본듯한 느낌에 여러삽질을 해보다가 결국 그래프 문제인가..? 라는 생각까지는 했는데, 위상정렬까지는 도달하지 못했다.

작년 알고리즘 시간에 배워본 적 있는 알고리즘이었다. 특정 순서를 만족하는 정렬상태를 구현할 수 있다.

방법은 다음과 같다.

1. 그래프를 구성한다. (단방향그래프여야 한다.)

2. 각 노드별로 진입 간선의 개수를 카운트 한다.

3. 진입간선이 0개인 노드부터 차례로 탐색한다.

   • 3-1. 해당 노드와 연결된 노드들의 진입간선을 지우고 개수를 업데이트한다.
   • 3-2. 3-1과정에서 진입간선의 개수가 0이 된다면 다음 턴의 탐색 지점으로 지정한다.

4. 더이상 탐색할 노드가 없을 때까지 반복한다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define endl "\n"

using namespace std;

int N, M;
int countLink[32023];
vector<int> G[32023];
vector<int> answer;
priority_queue<int, vector<int>, greater<int>> PQ;

void Solve() {
    cin>>N>>M;
    int a, b;

    for(int i=0; i<M; i++){
        cin>>a>>b;
        G[a].push_back(b);
        countLink[b]++;
    }

    for(int i=1; i<=N; i++) if(countLink[i] == 0) PQ.push(i);

    while(!PQ.empty()){
        int size = PQ.size();
        for(int i=0; i<size; i++){
            int n = PQ.top(); PQ.pop();
            answer.push_back(n);
            for(int j=0; j<G[n].size(); j++){
                if(--countLink[G[n][j]]==0) PQ.push(G[n][j]);
            }
        }
    }

    for(int ans: answer) cout<<ans<<" ";
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}

위상정렬 알고리즘을 복기할 수 있었다. 이론상으로만 배웠던 알고리즘이라 직접 구현해봄으로써 조금 더 오래 잘 기억할 수 있을 듯 하다.