(c++) 위상 정렬 2252번: 줄 세우기

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

 

문제 개요

 

위상 정렬 문제

 

위상 정렬이란 순환하지 않는 유향 그래프를 방향성에 거스르지 않도록 순서대로 배치하는 방법

 

즉 단방향 그래프 여러 개를 순서대로 배치하는 것

 

문제는 기본적인 위상 정렬을 풀이하는 것을 알고서 풀면 된다.

 

문제 각 노드들의 진입 차수와 진출 차수 중 진입 차수를 알면 된다.

(진입 차수 : 해당 노드로 들어오는 수  [ -> 노드] 

 진출 차수 : 해당 노드에서 나가는 수   [ 노드 -> ] )

진입 차수가 없다는 것은 부모가 없는 노드이기에 배치에서 상관쓰지 않으면 된다.

 

이 문제는 큐를 사용하여 풀이한다. 큐의 선입선출을 사용

 

1. 진입 차수를 계산 후 0인 노드를 큐에 삽입

2. 큐의 .pop 를 사용해서 제거

3. 제거된 노드의 자식 노드의 진입 차수를 -1

4. -1된 자식 노드 중 진입 차수가 0이 된 노드를 큐에 다시 넣는다.

5. 큐가 비었다면 끝

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define MAX 32001

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> graph[MAX];
    int in[MAX] = {0,}; // 진입 차수 계산
    // fill_n(in, MAX, 0);
    vector<int> result;
    queue<int> q;   

    for (int i = 0; i < m; i++) {
        int A, B;
        cin >> A >> B;
        graph[A].push_back(B); // 순방향 A -> B
        in[B] += 1; // 진입 차수 +1
    }
    
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int front = q.front();
        result.push_back(front);
        q.pop();
        for (int i : graph[front]) {
            in[i] -= 1;
            if (in[i] == 0) {
                q.push(i);
            }
        }
    }

    for (int x : result) {
        printf("%d ", x);
    }

    return 0;
}

 

일반 이중 배열 사용시 메모리 초과가 발생하기(32000 * 32000를 선언하기에)에 벡터를 사용하여 해결해야 한다.