[BOJ / C++] 2252번 : 줄 세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

Solved.ac 레벨

골드 III

풀이

골드 3으로 올라오니 그래프 이론 문제가 상당히 많이 보인다. 기존 실버 ~ 골드 하위 레벨의 그래프 이론 문제는 DFS, BFS, 다익스트라를 적절히 사용하는 방법을 배워오는 과정이라면 이제는 확실히 그래프에 대한 깊은 탐색이 이뤄지는 느낌...

아무튼, 이 문제는 그 중에서도 위상 정렬(Toplogy Sort)에 대한 문제다.

위상 정렬은 대학 선수 과목 등 조건이 있는 그래프의 정렬이 필요할 때 사용되는 것 같다.

스택(Stack)으로 구현하는 DFS, 그리고 큐(Queue)으로 구현하는 BFS를 활용할 수 있다.

또한 그래프에서 사이클이 발생하면 해당 그래프는 위상 정렬을 이용한 정렬이 불가능하다.

아직 깊은 공부가 되지 않은 상태이기 때문에 내가 아는 것은 여기까지...

 

따라서 이 문제 또한 조건이 있는 그래프의 정렬이라고 할 수 있다.

두 학생이 키를 비교하여 작은 학생이 앞에 오는 것이 그 조건이라고 할 수 있지 않을까...

 

이번에도 역시 동빈나님의 강의가 큰 도움이 되어주었다.

늘 감사합니다...

출처 : https://blog.naver.com/ndb796/221236874984

큐에 들어갈 수 있는 정점은 진입차수 (degree)가 0인 정점이다. 첫 탐색에서는 시작 노드가 될 수 있겠다.

큐에 들어있는 원소를 꺼내 해당 정점에 연결된 모든 간선을 제거하면 다시 진입차수가 0인, 새로운 시작 노드가 생기며 해당 노드를 큐에 삽입 후 큐에 있는 원소가 없을 때까지 진입차수가 0인 정점을 찾아 큐에 삽입하고, 큐에서 꺼내 간선을 제거한 뒤 큐에 삽입하는 작업을 반복한다. 

 

Code

#include<bits/stdc++.h>
#define MAX 32001

using namespace std;

int n, m;
vector<int> v[MAX];
vector<int> result;
int inDegree[MAX];
queue<int> q;

void topologySort() {
    for(int i = 1; i <= n; i++) {
        if(inDegree[i] == 0) q.push(i);
        //해당 노드의 진입차수가 0이라면 큐에 삽입한다.
    }

    while(!q.empty()) {
    	//큐가 빌 때까지 과정을 반복한다.
        int x = q.front();
        q.pop();
        
        //큐에서 원소를 꺼내 결과 배열에 push
        result.push_back(x);

        for(int i = 0; i < v[x].size(); i++) {
            int y = v[x][i];

            if(--inDegree[y] == 0) {
            	//다음 노드의 간선 제거 후 진입차수가 0이라면
                q.push(y);
            }

        }
    }
}

int main() {
    ios::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;
        v[a].push_back(b);
        inDegree[b]++;
    }

    topologySort();

    for(int i : result) {
        cout << i << " ";
    }

    return 0;
}

2252번: 줄 세우기