백준 1766 문제집 (위상정렬)

 

1번부터 N번까지의 문제가 있을 때, 문제를 푸는 순서를 구해주세요.

조건 1.  N개의 문제는 모두 풀어야한다

조건 2.  먼저 푸는 것이 좋은 문제가 있다면 먼저 풀어준다.

조건 3.  가능하면 쉬운 문제부터 푼다 (1 ~ N 순서로 난이도 상승)

---

해당 문제는 위상 정렬 알고리즘을 통해 풀이하는 문제입니다.

위상정렬에 대해서 모른다면 아래 링크에서 확인할 수 있습니다.

위상 정렬 알고리즘

 

---

풀이 방법

 

문제를 이해하기 위해 조건 2를 지워보겠습니다.

"먼저 푸는 것이 좋은 문제가 있다면, 먼저 푸는 것이 좋은 문제를 반드시 풀어야 한다."

위 조건이 없다면 위상정렬을 할 필요도 없이 반복문을 통해 1 ~ N까지 출력해주면 문제가 해결 됩니다.

즉, 이 문제의 핵심은 "순서대로 출력해준다" 입니다.

 

순서를 어떻게 정의해야할까

"순서대로 출력해준다"가 핵심이지만, 조건 2에 의해서 순서가 꼬이게 됩니다.

예를 들어 입력으로 2 -> 4가 들어왔을 때 위상 정렬의 진출 노드로 순회를 하게되면

1 -> 2 -> 4 -> 3 -> 5가 될 것입니다. 하지만, 2 -> 4를 입력으로 받았다고 하더라도, 

4보다 3이 우선순위가 높기 때문에 1 -> 2 -> 3 -> 4 -> 5가 나와야 할 것 입니다.

즉, 해당 문제는 우선 순위를 실시간으로 보장해주는 자료구조를 사용할 필요가 있습니다.

 

우선 순위를 보장하며 위상정렬

이 문제에 어려움을 겪으신 분들은 조건2와 조건3을 충족하기 위해서

1->2,   1->3,   1->4,   1->5
2->3,   2->4,   2->5
3->4,   3->5
4->5

위와 같은 우선순위를 진입, 진출 노드로 정의한 이후에 문제를 풀었을 것입니다.

하지만, 이 문제의 핵심은 "순서대로 출력해준다"입니다.

 

입력받은 간선들을 진입, 진출 노드로 정의 해주고

입력받지 않은 노드들을 포함해서 진입차수가 0인 노드들을 우선순위 큐에 넣게 되면

우선순위를 항상 보장 받을 수 있게 됩니다.

 

이후에 우선순위 큐에서 노드를 꺼내고, 그 노드를 기준으로 진출할 수 있는 노드들을 다시 큐에 넣어준다면

조건2와 조건3을 한번에 충족할 수 있게 됩니다.

 

정답 코드

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        int[] inDegree = new int[N + 1];
        List<int>[] outVtx = new List<int>[N + 1];
        for (int i = 1; i <= N; i++)
            outVtx[i] = new List<int>();


        for (int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split(' ');
            int A = int.Parse(input[0]);
            int B = int.Parse(input[1]);

            inDegree[B]++;
            outVtx[A].Add(B);
        }

        StringBuilder sb = new StringBuilder();
        PriorityQueue pq = new PriorityQueue();

        for (int i = 1; i <= N; i++)
        {
            if (inDegree[i] == 0)
                pq.Add(i);
        }

        while (!pq.IsEmpty())
        {
            int cur = pq.Pop();
            sb.Append(cur + " ");

            foreach (int nxt in outVtx[cur])
            {
                inDegree[nxt]--;
                if (inDegree[nxt] == 0)
                    pq.Add(nxt);
            }
        }
        sb = sb.Remove(sb.Length - 1, 1);
        Console.WriteLine(sb.ToString());
    }

}

 

 

우선순위 큐

public class PriorityQueue
{
    public void Add(int value)
    {
        arr[size++] = value;

        int cur = size - 1;

        while (cur > 0)
        {
            int parent = (cur - 1) / 2;

            if (arr[parent] > arr[cur])
            {
                int temp = arr[cur];
                arr[cur] = arr[parent];
                arr[parent] = temp;

                cur = parent;
            }
            else
                break;
        }
    }



    public int Pop()
    {
        int ret = arr[0];
        arr[0] = arr[--size];

        int cur = 0;

        while (cur < size - 1)
        {
            int left = cur * 2 + 1;
            int right = left + 1;

            if (left >= size)
                break;

            if (right < size && arr[right] < arr[left])
                left = right;

            if (arr[left] < arr[cur])
            {
                int temp = arr[left];
                arr[left] = arr[cur];
                arr[cur] = temp;

                cur = left;
            }
            else
                break;
        }

        return ret;
    }

    public bool IsEmpty() => size == 0;
    public int Count() => size;

    int size = 0;
    int[] arr = new int[100000];
}