[백준 2252 C++][G3] 줄 세우기

⭐️ 난이도

 

Gold 3

---

⭐️ 문제

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

2252번: 줄 세우기

 

---

⭐️ Idea flow

 

위상 정렬에 대해 이해하고 있고, 언제 이용해야 하는지 알고 있으면 해결할 수 있는 문제였다.

 

 

왜 위상 정렬을 이용하여 해결해야 하는가?

이 문제는 일부 학생들의 키 순서가 주어졌을 때, 전체 학생을 키 순서대로 줄을 세운 결과를 반환해야 한다.

방법이 여러 가지인 경우 아무거나 출력하면 되므로, 주어진 키 순서만 제대로 정렬하면 된다.

위상 정렬은 DAG(Directed Acyclic Graph) 즉, 사이클이 없는 방향 그래프에서 순서가 있을 때 사용하는 알고리즘이다.

문제에서도 두 노드(학생)을 방향이 있는 간선으로 연결한다. 따라서 이 경우에서 사용하면 적절하다.

 

 

[전체적인 알고리즘]

1. 입력을 받으면서 방향이 있는 간선을 연결해주고, 진입 차수를 설정해준다.

2. 위상 정렬을 한다.

   1) 시작하기 전에 진입 차수가 0인 노드를 큐에 삽입한다.

   2) 큐에서 하나씩 꺼내면서 방문한다. 이 때, 방문 결과를 저장하는 변수(result)에 현재 노드를 저장한다.

   3) 현재 방문하고 있는 노드와 연결된 노드들의 진입 차수를 1씩 줄여준다.

   4) 진입 차수가 0인 노드를 큐에 삽입한다.

3. 방문 결과를 저장한 변수(result)에 저장된 수들을 차례대로 출력한다.

 

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

// 2252 - 줄 세우기
int n, m; // 학생의 수, 키를 비교한 횟수
vector<int> inDegree, result;
vector<vector<int>> graph; // 간선의 정보


void input(){
    cin >> n >> m;
    inDegree.assign(n + 1, 0);
    result.assign(n + 1, 0);
    graph.assign(n + 1, vector<int>(0, 0));

    for(int i = 0; i < m; i++){
        int a, b; // a가 b의 앞에 서야 한다
        cin >> a >> b;
        graph[a].emplace_back(b);
        inDegree[b]++;
    }
}

void topology_sort(){
    queue<int> q;
    // 진입차수가 0인 정점들을 큐에 삽입
    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0)    q.push(i);
    }

    for(int i = 0; i < n; i++){
    	// 총 n번 반복하기 전에 큐가 비어있다면 사이클이 있다는 것
        if(q.empty())   return;
        int cur = q.front(); // 현재 방문한 노드의 번호
        result[i] = cur; // 방문 결과 저장
        q.pop();

	// 현재 노드와 연결된 노드 중 진입차수가 0인 노드가 있다면 큐에 삽입
        for(int k = 0; k < graph[cur].size(); k++){
            int next = graph[cur][k];
            if(--inDegree[next] == 0)   q.push(next);
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    topology_sort();

    for(int i = 0; i < n; i++){
        cout << result[i] << " ";
    }

    return 0;
}