백준 1766번: 문제집 (C++)

문제링크

https://www.acmicpc.net/problem/1766

백준 1766번 문제는 "문제집"이라는 제목으로 알려진 위상 정렬 문제입니다. 주어진 문제들을 풀기 위해 반드시 풀어야 하는 선행 문제들의 순서를 구하는 문제입니다.

풀이방법

이 문제는 위상 정렬 알고리즘을 사용하여 해결할 수 있습니다. 위상 정렬은 그래프의 노드들을 방향성을 유지하면서 정렬하는 알고리즘으로, 선후 관계가 있는 작업들을 순서대로 수행해야 할 때 유용하게 사용됩니다.

문제의 조건에 따르면 "문제를 풀기 전에 반드시 풀어야 하는 문제가 있다"는 조건이 있습니다. 이는 위상 정렬을 통해 문제를 풀어야 함을 의미합니다. 따라서 다음과 같은 접근 방법으로 문제를 해결할 수 있습니다.

1. 입력으로 주어진 문제들의 선행 관계를 그래프로 표현합니다. 이를 위해 인접 리스트를 사용합니다.
2. 각 노드의 진입 차수를 기록하는 배열을 초기화합니다. 진입 차수란 특정 노드로 들어오는 간선의 개수를 의미합니다.
3. 진입 차수가 0인 노드들을 큐에 넣습니다. 이는 선행 문제가 없는 문제들을 의미합니다.
4. 큐에서 노드를 하나씩 꺼내면서 해당 노드와 연결된 노드들의 진입 차수를 감소시킵니다.
5. 진입 차수가 0이 된 노드들을 큐에 넣습니다.
6. 큐가 빌 때까지 위 과정을 반복합니다.
7. 큐에서 꺼낸 노드들의 순서를 기록하는 배열에 추가합니다.
8. 결과 배열을 출력합니다.

위의 접근 방법을 코드로 구현하면 문제를 해결할 수 있습니다.

코드

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

vector<int> adj[32005];
vector<int> result;
int indegree[32005]; // 각 노드의 진입 차수를 기록하는 배열
int n, m, u, v;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    while (m--)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        indegree[v]++; // 각 노드의 진입 차수를 증가시킴
    }

    priority_queue<int, vector<int>, greater<int>> pq; // 우선순위 큐를 사용하여 작은 번호의 노드부터 방문하도록 함

    for (int i = 1; i <= n; i++)
    {
        if (indegree[i] == 0) // 진입 차수가 0인 노드를 큐에 넣음
        {
            pq.push(i);
        }
    }

    while (!pq.empty())
    {
        int cur = pq.top(); //
        pq.pop();
        result.push_back(cur); // 방문한 노드를 결과 벡터에 추가

        for (auto nxt : adj[cur])
        {
            indegree[nxt]--; // 현재 노드와 연결된 노드의 진입 차수를 감소시킴

            if (indegree[nxt] == 0) // 진입 차수가 0이 되면 큐에 넣음
            {
                pq.push(nxt);
            }
        }
    }

    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << ' ';
    }

    return 0;
}