[BOJ알고리즘, C++]#14567_선수 과목(Prerequisite), 위상 정렬, 비순환 유향 그래프, DAG

 

#1. 문제

14567번: 선수과목 (Prerequisite)

 

---

 

#2. 풀이

 

1. 위상 정렬

[자료구조]#6_그래프

 

위상 정렬은 비순환 유향 그래프(DAG)에서 각 정점의 선행 관계를 유지하며 정점들을 나열하는 방법입니다. 일반적으로, 위상 정렬은 DFS와 진입 차수 BFS를 활용합니다.

2. 위상 정렬 과정에서 각 과목의 이수 학기를 기억해 놓자!

 

1. 진입 차수 BFS를 활용해 주어진 정점들에 대하여 그래프를 구성하고, 위상 정렬을 수행합니다.
2. 이때, 현재 정점의 인접 정점을 순회하는 BFS 과정에서 인접 정점들의 이수 가능 학기와 현재 정점의 이수 학기 + 1과 비교하여 최대 값으로 갱신해줍니다.
3. 위상 정렬이 모두 끝난 시점에 각 정점의 이수 학기를 저장한 배열을 순회하며 정답을 출력합니다.

 

---

 

#3. 코드

 

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

int N, M;
vector<vector<int>> graph;
vector<int> InDegree;

void TopologicalSort()
{
    queue<int> q;
    vector<int> season(N + 1, 0);

    // #1. 진입 차수가 0인 정점들을 큐에 삽입합니다.
    for (int i = 1; i <= N; ++i)
    {
        if (InDegree[i] == 0)
        {
            season[i] = 1;
            q.push(i);
        }
    }

    // #2. 큐 순회
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (const auto neighbor : graph[cur])
        {
            InDegree[neighbor]--;
            // #3. 진입 차수가 0이 되면, 최소 이수 가능 학기 계산 및
            if (InDegree[neighbor] == 0)
            {
                season[neighbor] = max(season[neighbor], season[cur] + 1);
                q.push(neighbor);
            }
        }
    }

    for (int i = 1; i <= N; ++i)
        cout << season[i] << ' ';
}

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

    cin >> N >> M;

    graph.resize(N + 1);
    InDegree.resize(N + 1, 0);

    while (M--)
    {
        int first, second;

        cin >> first >> second;
        graph[first].push_back(second);
        InDegree[second]++;
    }

    TopologicalSort();

    return 0;
}

 

---