9주차(위상정렬) - [C++]백준14567 선수과목

12 May 2022 in Study on Algorithm

백준14567 선수과목 링크

문제

예제 입력

---

코드

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

// 각 선수강 수, 학기결과
int cnt[1001], result[1001];
// 인접행렬
vector<int> vec[1001];
int n, m;

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

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

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

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

    cin >> n >> m;
    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        vec[a].push_back(b);
        cnt[b]++;
    }
    topology_sort();
}

설명

이 문제는 위상정렬의 개념으로 어떤 과목들은 선수과목이 있어 먼저 이수해야만 해당 과목을 이수할 수 있다는 것이 시간표에 대한 우선순위로 이수 순서를 정하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 queue를 사용하여 구현했습니다. 위상정렬이라는 개념을 사용해서 풀 것인데 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것입니다. 즉, 방향이 있어서 앞에 작업을 끝내지 않으면 다음 일을 못합니다. 위상정렬를 하기 위해서는 인접행렬과 몇개의 선작업이 있는지 저장하는 배열이 필요하고 그것으로 선작업이 없는 것들을 먼저 큐에 넣어서 실행시킵니다. 그 후에는 앞에서 했던 작업이 선작업으로 지정됬던 다음 작업을 지금 할 수 있는지 아니면 또 다른 선작업이 있는지 확인하며 최종적으로 결과들을 저장했던 것을 출력합니다.

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

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

---

결과