[ 백준 14567 ] 선수과목, Prerequisite (C++) - 위상정렬

---

🔗 문제 링크

14567번: 선수과목 (Prerequisite)

---

💡 문제 풀이 및 해석

1. 문제부터 선수과목이라고 써져 있는 것을 보니, 위상정렬 문제임을 알 수 있다. (많이 풀어본 경험으로써??)
2. 위상정렬이라고 마냥 어렵게 생각할 것 없다. 과목 A를 해결하면 과목 B를 배울 수 있다는 조건을 보자.
3. A -> B 라고 생각하자. 그러면 화살표를 받는 B는 선수과목의 숫자가 +1이 되는 것이다. 그러면, 이는 선수과목의 숫자가 0이라면 수강할 수 있다는 뜻이 되기도 한다.
4. 3번 해석을 input()에 적용시켰다. X가 선수과목해야 하는 숫자다. (적당한 이름이 떠오르지 않아서 임의로 해놨다가 그대로 풀어버렸다...)
5. 그리고 canLearn이라는 변수명과 같이 배울 수 있는 과목들을 따로 모와놓는다.
6. 배울 수 있는 과목들을 이번 학기에 모두 배우고 다음학기(cnt)로 넘겨준다. 이때, 과목을 배우고 선수과목을 줄여줄 때, 그 과목이 더 이상 배워야 할 선수과목이 없다면 canLearn에 추가시켜 준다.
7. 6번 과정을 반복해 주면 answer에 각각 몇 학기에 배울 수 있는지 나온다.

---

⭐️ 정답 코드 및 설명

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

int N, M;
vector<vector<int>> postLearn;
vector<int> X;
queue<int> canLearn;
vector<int> answer;

void input() {
    cin >> N >> M;
    postLearn = vector<vector<int>>(N + 1,vector<int>()); // 이 과목을 배우면 선수과목이 삭제되는 것들
    X = vector<int>(N + 1, 0);
    answer = vector<int>(N + 1);
    for (int i = 0; i < M; i++) {
        int A, B; cin >> A >> B; // B를 배우기 위해서는 A를 배워야함.
        postLearn[A].push_back(B); // A를 배우면 B의 선수과목 삭제
        X[B]++; // 선수과목의 숫자
    }
    for (int i = 1; i <= N; i++) {
        if (X[i] == 0) canLearn.push(i); // 선수과목이 없다면 배울 수 있음
    }
}

void sol() {
    int cnt = 1;
    while (!canLearn.empty()) {
        int Size = canLearn.size();
        for (int i = 0; i < Size; i++) {
            int cur = canLearn.front(); canLearn.pop();
            answer[cur] = cnt;
            for (int j : postLearn[cur]) {
                X[j]--; // 선수과목 이수
                if (X[j] == 0) canLearn.push(j); // 선수과목이 더 이상 없다면, 배울 수 있음
            }
        }
        cnt++;
    }
}

int main() {

    input();
    sol();

    for (int i = 1; i <= N; i++)
        cout << answer[i] << " ";
    return 0;
}

---

🤔 문제 후기

음,,, 위상정렬 문제인데, A, B 관계를 처음에 반대로 하여서 선수과목을 배우면 그 과목을 지워주는 방식으로 문제를 풀려했는데, 그러면 find를 사용하고 또 조건문을 쓰고 하다 보면, 문제는 맞아도 시간적으로 더 오래 걸릴 것이라 생각해 중간에 다 지우고 다시 풀었다. 개인적인 생각이지만, find를 사용하고 문제를 풀었으면, 아마 지우고 다시 푼 시간보다 훨씬 오래 걸렸을 것 같다.(오류가 생겼을지도??) 다행히 이 방식은 한 번에 테스트케이스가 모두 통과하고 문제도 통과해서 다행이었다.