1766-문제집

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

1766번: 문제집

본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다.

 

본 문제는 조건에 따라 작업의 순서를 구하는 문제입니다.

순서가 정해져있는 작업을 풀때 우리는 위상 정렬(Topology Sort) 알고리즘을 사용할 수 있습니다.

문제를 풂에 앞서 저는 나동빈님의 위상 정렬 강의를 수강하였습니다.

 

 

 

먼저, 문제에 맞게 그래프를 구성해야합니다.

 

예제를 기준으로 그래프를 구성해보겠습니다. 

 

입력
4 2

4 2

3 1

 

먼저 푸는 것이 좋은 문제에 대한 정보에 대해 잠시 생각을 미뤄봅시다. 그러면 우리는 N=4 일때 아래의 그래프를 떠올릴 수 있습니다. 문제의 조건 3. "가능하면 쉬운 문제부터 풀어야 한다." 에 의하여 각 노드간의 연결은 낮은 숫자를 갖는 노드에서 그 다음 높은 숫자를 갖는 노드로 정의됨을 알 수 있습니다.

그림 1. 예제 입력에 따른 그래프 구성도, 먼저 푸는 것이 좋은 문제에 대한 정보를 반영하지 않은 경우 

 

실제로 문제를 푸는데 있어 이러한 연결을 갖지는 않기에 노드간 에지를 회색 점선으로 표현하였습니다.

 

그런데, 먼저 푸는 것이 좋은 문제에 대한 정보를 추가하여 그래프를 구성하게 되면 그래프는 아래와 같이 변하게 됩니다.

 

그림 2. 예제 입력에 따른 그래프 구성도, 먼저 푸는 것이 좋은 문제에 대한 정보를 반영한 경우 

해당 상태에서 위상 정렬 알고리즘을 적용합니다. 이때, 조건 2. 를 만족하면서 조건 3. 을 만족해야 합니다. 그렇게 하기 위해서 위상 정렬 알고리즘의 구현에 있어 Queue 대신에 Priority Queue 를 사용합니다. 이때, 우선순위을 정하는 순은 크기의 내림차순입니다. 이렇게 하면, 진입차수(In-Degree) 가 0 이면서 크기가 낮은 노드를 먼저 방문하기때문에 자연스럽게 조건 2. 를 만족하면서 조건 3. 을 만족하게 됩니다.

 

그림 2. 상으로는 1번 노드와 4번 노드 간에 연결이 끊겨있습니다. 이는 조건 2. 와 조건 3.을 풀어감에 따라 동적으로 그래프 연결이 정의되기 때문에 곧바로 노드간에 연결을 정의할 수 없기 때문이며, 실제로는 알고리즘을 통해 3 -> 1 -> 4 -> 2 순으로 노드 간 연결이 정의되어야 합니다.

 

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    int N; //문제의 수(1<= N <= 32000)
    int M; //먼저 푸는 것이 좋은 문제에 대한 정보의 개수(1<= M <= 100000)

    cin >> N >> M;

    vector<vector<int>> g(N+1);
    priority_queue<int, vector<int>, greater<int>> q;//우선순위큐(FIFO), 내림차순
    vector<int> indegree(N+1, 0);
    
    // p_a 번 문제는 p_b 번 문제보다 먼저 푸는 것이 좋다. 정보를 그래프로 나타냄
    for(int i = 0; i < M; i++)
    {
        int p_a;
        int p_b;

        cin >> p_a >> p_b;
        g[p_a].push_back(p_b);//from: p_a, to: p_b
        indegree[p_b]++;
    }

    for(int i = 1; i <= N; i++)
        if(indegree[i]==0)
            q.push(i);
    
    while(!q.empty())
    {
        int problem = q.top();
        q.pop();
        cout << problem <<" ";

        for(auto next_problem:g[problem])
        {
            indegree[next_problem] -= 1;
            if(indegree[next_problem] == 0)
                q.push(next_problem);
        }
    }

    return 0;
}