[백준/Baekjoon] 2252 줄 세우기 C++ :: topological Sort

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

2252번: 줄 세우기

---

1. Logic

대표적인 위상정렬 문제

 

위상정렬이란?

비순환 방향 그래프(DAG: Directed Acyclic Graph)에서 정점을 선형으로 정렬하는 것. 만약 그래프가 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다.
모든 간선(u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다.

 

나는 BFS를 사용하는 방식으로 풀이했다. 

 

BFS를 사용한 위상정렬 방식은 

1. 모든 정점의 inDegree를 설정해준다. (inDegree : 정점으로 들어오는 간선 수)

2. 한 간선을 처리한 후 inDegree를 --해준다.

3. inDegree가 0인 정점은 방문한 것으로 표시하고 큐에 정점을 추가한다.

4. 이후 큐가 빌때까지 반복한다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m;

vector<int> graph[32001];
//정점으로 이어진 간선 수
int inDegree[32001];

void topologicalSort() {
    queue<int> q;

    for(int i = 1; i <= n; i++) {
        if(!inDegree[i]) 
            q.push(i);
    }

    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        cout << cur << " ";

        for(int i = 0; i < graph[cur].size(); i++) {
            inDegree[graph[cur][i]]--;
            if(!inDegree[graph[cur][i]]) {
                q.push(graph[cur][i]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        graph[a].push_back(b);
        inDegree[b]++;
    }

    topologicalSort();
}

---

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90