문제집 (1766번) - 백준 (BOJ)

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

1766번: 문제집

 

백준 - 문제집 (1766번)

 

난이도 : Gold 2

알고리즘 : Topological Sorting (위상 정렬), Priority Queue (우선순위 큐)

풀이 소요 시간 : 60 mins

Time Complexity : O( M + {N * log(N)} )

 

import sys
input = sys.stdin.readline
print = sys.stdout.write
from heapq import heapify, heappush, heappop


def _pop():
    # 3
    p = heappop(pq)
    for c in graph[p]:
        dgr[c] -= 1
        if not dgr[c]:
            heappush(pq, c)
    return str(p)


if __name__ == '__main__':
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    dgr = [0] * (N+1)
    
    # 1
    for _ in range(M):
        p, c = map(int, input().split())
        graph[p].append(c)
        dgr[c] += 1
    
    # 2
    pq = [i for i in range(1, N+1) if not dgr[i]]
    heapify(pq)
    print(' '.join(_pop() for _ in range(N)))

 

1.

입력으로 주어지는 M 개의 정보를 통해,

graph에 각 노드의 자식 노드들을 저장하고

dgr에 각 노드로 들어오는 간선(edge)의 개수를 저장한다.

 

2.

dgr 값이 0인 노드들을 우선순위 큐인 pq에 넣고,

N번의 반복문을 실행한다. (for 문)

 

3.

1~N 중 i 번째 단계에서는,

현재 pq에서 숫자가 가장 작은 노드 p를 하나 꺼낸다.

이 p가 바로 i번째 순위의 문제 번호 (노드) 이다.

(여기서 pq는, 현재 노드로 들어오는 간선의 개수가 0인 노드들만 저장한다.)

 

그리고 graph에서 p의 자식 노드 c 들을 하나씩 찾아서, ( for c in graph[p]: )

c로 들어오는 간선의 개수를 하나씩 빼준다. ( dgr[c] -= 1 )

(왜냐하면 부모 중 하나인 p는 이미 확인했기 때문에)

 

그리고 현재 c로 들어오는 간선이 하나도 없다면, ( if not dgr[c]: )

c를 pq에 넣어준다. ( heappush(pq, c) )

 

---

 

정말 오랜만에 위상 정렬 (Topological Sorting) 을 활용하는 문제였다.

위상 정렬과 우선순위 큐를 적절히 활용해서 해결할 수 있었다.