백준 1766번 : 문제집

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

1766번: 문제집

위상 정렬의 개념을 알고, 이 문제에 적용할 수 있으면 쉽게 풀 수 있는 문제였다.

 

총 N개의 문제가 있고 문제는 1번부터 N번까지 난이도를 기준으로 오름차순 정렬돼있다. N개의 모든 문제를 풀되, 가장 쉬운 문제(번호가 낮은 문제)부터 풀어야 하지만 어떤 문제는 그 문제보다 선행되어 풀어야 하는 문제가 존재한다. 즉 선행 문제를 풀기 전엔 해당 문제를 풀 수 없다. 이 규칙들을 지켜가면서 문제 푸는 순서를 출력해야한다.

 

일단 먼저 N개의 문제를 선행문제와 비선행문제로 나눠보자. 선행문제는 자신들보다 먼저 풀어야 하는 문제가 존재해서 당장 풀 수 없는 문제들을 말하고, 비선행문제는 그렇지 않아서 지금 당장이라도 풀 수 있는 문제를 말한다. 매번 우리는 풀 수 있는 문제들(비선행 문제) 중 가장 번호가 낮은 문제를 풀어야 한다. 문제를 풀고나면 비선행 문제의 목록을 갱신해줘야 한다. 왜냐하면 문제를 품으로써 당장 풀 수 있게 된 또 다른 문제가 생길 수 있기 때문이다. 즉, 여기서 선행문제는 진입차수가 1 이상인 노드를 의미하고 비선행문제는 진입차수가 0인 노드를 의미한다. 

 

더 알기 쉽게 게임으로 비유를 해보자. 일반적으로 RPG에서는 레벨이 낮을때부터 배울 수 있는 하위 스킬과 특정 조건을 만족해야만 해금할 수 있는 상위 스킬이 있다. 상위 스킬은 몇가지 하위 스킬을 배운 상태에서만 습득할 수 있다. 여기서 하위 스킬은 조건 없이 풀 수 있는 문제이고, 상위 스킬은 선행문제를 풀어야만 풀 수 있는 문제이다. 

 

우선순위 큐를 이용해 진입차수가 0인 노드를 큐에 삽입하고, 노드 번호가 낮은 순서대로 꺼내어 그 노드와 연결된 다른 노드의 진입차수를 감소시킨다. 계산 후 진입차수가 0인 노드가 생기면 큐에 삽입하고 큐가 빌 때까지(모든 문제를 풀 때까지) 과정을 반복한다. 큐에서 꺼낸 노드와 연결된 노드를 확인하는데 총 M번 반복하고, 매번 반복마다 최대 logN 만큼의 시간이 소요되므로 시간복잡도는 O(MlogN)이다. 

import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
d = [[[], 0] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    d[a][0].append(b)
    d[b][1] += 1

q = [i for i in range(1, n+1) if d[i][1] == 0]

while q:
    k = heapq.heappop(q)
    print(k, end=' ')
    for i in d[k][0]:
        d[i][1] -= 1
        if not d[i][1]:
            heapq.heappush(q, i)