[백준] 2252번 줄 세우기

 

 

문제

소스코드

#include<iostream>
#include<vector>
#include<queue>
constexpr int MAX_N = 32001;
 
std::vector<int> g_nodes[MAX_N];
std::vector<int> g_result;
int g_weight[MAX_N];
 
void TopologySort(int N) {
    std::queue<int> q;
 
    //가중치가 0인 노드를 찾아서 queue에 넣는다.
    for (int i = 1; i <= N; ++i) {
        if (g_weight[i] == 0) {
            q.emplace(i);
        }
    }
    //N개의 노드를 방문
    for (int i = 1; i <= N; ++i) {
 
        auto front_value = q.front();
        q.pop();
        g_result.emplace_back(front_value);
        //해당 노드와 연결된 노드의 가중치를 제거한다.
        for (const auto& i : g_nodes[front_value]) {
            g_weight[i]--;
            if (g_weight[i] == 0) {
                q.emplace(i);
            }
        }
    }
}
 
int main() {
    int N, M;
    std::cin >> N >> M;
    
 
    for (int i = 0; i < M; ++i) {
        int lhs, rhs;
        std::cin >> lhs >> rhs;
        // lhs<---rhs
        g_nodes[lhs].emplace_back(rhs);
        g_weight[rhs]++;
    }
    TopologySort(N);
    for (const auto& i : g_result) {
        std::cout << i << " ";
    }
}

 

후기

이 문제를 해결하기 위한 키워드는 TopologySort(위상 정렬)이다.

 

위상 정렬이란 DAG(Directed Acyclic Graph, 사이클이 없는 방향 그래프)에 대해 정점의 순서를 나열하는 알고리즘이다.

자세한 알고리즘에 대한 설명은 생략한다.

 

위상 정렬 알고리즘을 이용해서 문제를 풀어보았다. 위상 정렬을 잘 사용하면 RPG 게임에서 스킬 트리를 구현하는데 도움이 될 거 같다.

 

 

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/2252

 

관련 글

[자료구조 알고리즘/그래프(Graph)와 트리(Tree)] - 그래프(Graph)

[자료구조 알고리즘/큐(Queue)와 스택(Stack)] - [Queue]간단한 Queue 구현