백준 2252 - 줄 세우기

문제 설명

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N명의 학생을 M개의 관계로 줄을 세우는 문제이다.

하지만, M개의 관계가 N명의 모든 학생을 나타내기엔 부족할 수 있다.

 

해당 문제는 위상 정렬을 이용하면 풀 수 있다. 

위상 정렬이란 방향 그래프의 노드에 대해 순서를 매기며 정렬하는 것을 말한다.

위상 정렬이 가능한 경우는 해당 그래프에 사이클이 존재하지 않다는 것과 정확히 같다.

 

해당 문제는 절대 사이클이 발생할 수 없다.

a > b, b > c 일 때, c > a는 불가능하기 때문이다.

즉, 사이클이 없다는 전제가 깔렸으니 위상 정렬을 수행할 수 있다는 뜻이 된다.

위상 정렬을 통해 노드를 정렬하면 문제에서 원하는 답을 도출할 수 있다.

 

위상 정렬은 다음과 같이 진행된다.

1. 그래프의 InDgree가 0인 노드를 모두 큐에 넣는다.
2. N번의 라운드를 진행하며 큐에서 하나의 요소씩 뽑아 결과에 기록한다. 
   1. 만약, 큐가 비어있다면 위상 정렬이 불가능한 그래프이다.
3. 하나의 요소가 빠지며 해당 요소와 연결된 노드의 InDgree를 줄인다.
   1. 만약, InDgree가 줄어 0이 되는 노드가 있다면 큐에 넣는다.

void TopologySort()
{
    queue<int> q;

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

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

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

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, M;

vector<int> inDegree;
vector<vector<int>> graph;
vector<int> result;

void TopologySort()
{
    queue<int> q;

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

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

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    graph.assign(N + 1, vector<int>());
    inDegree.assign(N + 1, 0);

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;

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

    TopologySort();

    for (auto num : result)
    {
        cout << num << " ";
    }

    return 0;
}

---