9주차(위상정렬) - [C++]백준2252 줄 세우기

15 May 2022 in Study on Algorithm

백준2252 줄 세우기 링크

문제

예제 입력

---

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

// 각 선작업수
int cnt[32001];
// 인접행렬
vector<int> vec[32001];
int n, m;

void topology_sort() {
    queue<int> q;
    // 처음 지점 추가
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << " ";
        // 다음 지점 탐색
        for (int i = 0; i < vec[cur].size(); i++) {
            int nxt = vec[cur][i];
            cnt[nxt]--;
            if (cnt[nxt] == 0) {
                q.push(nxt);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //vector<vector<int>> vec1;
    //vec1.resize(n + 1);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        vec[a].push_back(b);
        cnt[b]++;
    }
    topology_sort();
}

설명

이 문제는 학생들을 키 순서대로 줄을 세우는데 비교가 있는 일부 학생들만 순서를 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 queue를 사용하여 구현했습니다. 앞에서 했던 작업 문제와 거의 같은데 다른점은 현재 학생의 번호를 바로 출력합니다.

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과