[백준] 1766 - 문제집

1. 문제

1766번: 문제집

2. 개요

1번부터 N번까지의 문제가 있다.

문제들을 풀려고 하는데 다음과 같은 규칙이 있다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

이 때 문제 푸는 순서를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

위상 정렬 + 최소 힙 (우선순위 큐)을 이용한다.

선,후행관계에 따라 그래프를 만들어주면서 선행 문제는 문제는 그 때마다 진입간선을 1씩 늘려준다.

번호가 낮을수록 진입 간선이 0인 문제들을 힙에 넣는다.

힙에서 하나씩 문제를 빼내면서 후행 문제의 진입간선을 하나씩 줄여준다.

진입간선이 0이 된 문제가 있다면 이들 또한 힙에 넣어준다.

현재 탐색한 문제를 결과에 넣고 큐가 빌 때까지 이를 반복한다.

큐가 다 비어 반복문을 탈출했다면 답을 출력한다.

3-2. Python

import sys
import heapq
from collections import deque

N, M = map(int, sys.stdin.readline().split())

graph = [[] for i in range(N+1)]
inedge = [0 for i in range(N+1)]
q = []
result = deque()

for i in range(M):
    first, last = map(int, sys.stdin.readline().split())

    graph[first].append(last)
    inedge[last] += 1

for i in range(1, N+1):
    graph[i].sort(key = lambda x : x)

    if inedge[i] == 0:
        heapq.heappush(q, i)

while q:
    now = heapq.heappop(q)

    for nexts in graph[now]:
        inedge[nexts] -= 1
        if inedge[nexts] < 1:
            heapq.heappush(q, nexts)

    result.append(now)

print(*result)

3-3. C#

namespace boj_1766
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            List<List<int>> graph = new List<List<int>>();

            for (int i = 0; i < N + 1; i++)
                graph.Add(new List<int>());

            int[] inedge = new int[N + 1];
            PriorityQueue<int, int> q = new PriorityQueue<int, int>();
            List<int> result = new List<int>();

            for (int i = 0; i < M; i++)
            {
                string[] info = sr.ReadLine().Split();
                int start = int.Parse(info[0]);
                int last = int.Parse(info[1]);

                graph[start].Add(last);
                inedge[last]++;
            }

            for (int i = 1; i < N + 1; i++)
            {
                graph[i].Sort();

                if (inedge[i] == 0)
                    q.Enqueue(i, i);
            }

            while (q.Count > 0)
            {
                int now = q.Dequeue();

                foreach (int nexts in graph[now])
                {
                    inedge[nexts]--;

                    if (inedge[nexts] < 1)
                        q.Enqueue(nexts, nexts);
                }

                result.Add(now);
            }

            foreach (int r in result)
                sw.Write($"{r} ");

            sw.Close();
        }
    }
}