greentea31's Note

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

풀이 과정

N명의 학생 중 일부 학생의 키의 대소 여부가 주어질 때, 줄을 세우는 프로그램을 작성하는 문제이다.

A와 B의 키의 대소 관계를 비교했을 때, A가 B보다 작으면 정점 A에서 B로 가는 간선이 존재하는 그래프로 모델링할 때, 문제에서 주어진 상황을 모델링하면 Direct Acyclic Grpah(비순환 방향 그래프) 형태로 모델링 된다.

비순환 방향 그래프는 그래프의 방향성을 거스르지 않고 정점들을 나열하는 위상정렬이 가능하다. 위상 정렬은 각 정점을 우선순위에 따라 배치한 것으로, 일반적으로 결과가 유일하지 않은데, 답이 여러 가지인 경우 아무거나 출력하라는 문제 지문을 고려하면 위상 정렬의 결과 중 하나를 출력하라는 의도임을 알 수 있다.

위상 정렬을 시행 후 결과를 출력시켜 주었다. 위상 정렬을 구현할 때 일반적으로

1. 인접 리스트

2. In-degree 저장 배열

3. push, pop이 가능한 자료구조

의 3가지를 활용해서 구현한다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, temp;

    cin >> N >> M;
    vector<int> v[32001];
    queue<int> q;
    int inDegree[32001];

    for (int i = 0; i < N+1; i++) inDegree[i] = 0;

    int small, big;

    for (int i = 0; i < M; i++) {
        cin >> small >> big;
        v[small].push_back(big);
        inDegree[big]++;
    }

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

    while(!q.empty()) {
        temp = q.front(); q.pop();
        cout << temp << ' ';

        for (int i = 0; i < v[temp].size(); i++) {
            inDegree[v[temp][i]]--;
            if (inDegree[v[temp][i]] == 0) q.push(v[temp][i]);
        }
    }
    return 0;
}