백준 1005번 C++

• 위상정렬이란?

  • 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미 ex)대학의 선수과목

  • 진입 차수 (In-degree): 각 노드에 대해 들어오는 간선의 수를 나타내는 진입 차수를 계산합니다. 진입 차수가 0인 노드는 시작점이 됩니다.

  • 큐를 이용한 처리: 진입 차수가 0인 노드를 큐에 넣습니다. 그리고 큐에서 노드를 하나씩 빼면서 해당 노드에서 나가는 간선을 제거하고 도착 노드의 진입 차수를 감소시킵니다. 진입 차수가 0이 된 노드를 큐에 추가합니다.

  • 모든 노드를 방문: 큐가 빌 때까지 반복하면서 모든 노드를 방문합니다. 만약 큐가 비어도 아직 방문하지 않은 노드가 있다면, 그래프에 순환 구조가 존재한다는 의미입니다.

  • 순서 기록: 큐에서 꺼낸 노드를 순서대로 나열하면 위상 정렬된 순서를 얻을 수 있습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <random>
#include <map>
#include <set>

#pragma warning(disable: 4996)

using namespace std;

int indegree[1003];
map<int, int> resultCost;
map<int, int> cost;

int main() {
    // 테스트 케이스의 개수 입력
    int T;
    cin >> T;

    for (int i = 0; i < T; i++) {
        int answer = 0;

        // 노드의 개수(N)와 간선의 개수(K) 입력
        int N, K;
        cin >> N >> K;

        // 각 노드의 비용 입력 및 초기화
        vector<vector<int>> v(N + 1);
        queue<int> q;

        for (int j = 1; j <= N; j++) {
            scanf("%d", &node_cost);
            cost[j] = node_cost;
            resultCost[j] = node_cost;
        }

        // 간선 정보 입력 및 진입 차수 계산
        for (int j = 0; j < K; j++) {
            int x, y;
            scanf("%d %d", &x, &y);
            v[x].emplace_back(y);
            indegree[y]++;
        }

        // 목표 노드(W) 입력
        int W;
        cin >> W;

        // 진입 차수가 0인 노드 큐에 삽입
        for (int j = 1; j <= N; j++) {
            if (j == W)
                continue;
            else if (indegree[j] == 0) {
                q.emplace(j);
            }
        }

        // 위상 정렬 수행
        while (!q.empty()) {
            int idx = q.front();
            q.pop();

            for (int j = 0; j < v[idx].size(); j++) {
                int n = v[idx][j];

                // 최소 비용 업데이트
                resultCost[n] = max(resultCost[n], resultCost[idx] + cost[n]);
                if (--indegree[n] == 0)
                    q.emplace(n);
            }
        }

        // 결과 출력
        cout << resultCost[W] << endl;

        // 변수 초기화
        for (int j = 1; j <= N; j++) {
            indegree[j] = 0;
            resultCost[j] = 0;
            cost[j] = 0;
        }
    }

    return 0;
}