[백준 14567번] 선수과목 (C++)

문제링크 : https://www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

 

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

vector<int>v[1000];
int arr[1000];
int result[1000];
queue<int>q;

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

    int N, M, A, B;
    cin >> N >> M;
    while(M--)
    {
        cin >> A >> B;
        v[A].push_back(B);
        arr[B]++;
    }

    for(int i=1; i<=N; i++)
    {
        if(arr[i]==0) //진입차수가 0이면
        {
            q.push(i);
        }
        result[i]=1;
    }

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(int i=0; i<v[cur].size(); i++)
        {
            int next = v[cur][i];
            if(--arr[next]==0) //다음 값의 진입차수가 0이면
            {
                q.push(next);
                result[next] = result[cur] + 1;
            }
        }
    }


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

처음에 진입차수가 0인 값들을 큐에 넣어준다.

이후 해당 값들에 연결된 값들을 확인해준다.

연결된 값들은 간선이 제거되기에 1을 빼주고 이때 값이 0이 된다면 진입차수가 0이라는 것이므로 새롭게 큐에 넣어준다.

그리고 결과값을 저장하는 배열에 현재 값 + 1을 한 값을 넣어준다.