[BOJ] #1766 - 문제집

1766번: 문제집

 

 

** 문제 유형

• 힙, 위상 정렬

 

** 풀이

1. 전형적인 위상 정렬 문제
2. 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘
3. 위상 정렬의 시간 복잡도는 O(V + E)
4. 힙 == 우선순위 큐

 

+) 위상 정렬(Topology Sort) 알고리즘

1. 진입 차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내, 해당 원소와 간선을 제거
3. 제거 후 진입 차수가 0인 된 정점을 큐에 삽입
4. 큐가 빌 때까지 (2-3) 단계를 반복

- 모든 원소를 방문하기 전에 큐가 빈다면, 사이클 존재
- 모든 원소를 방문했다면, 큐에서 꺼내 순서가 위상 정렬의 결과

 

import heapq

n, m = map(int, input().split())

array = [[] for i in range(n + 1)]
indegree = [0] * (n + 1) # 진입 차수
heap = []
result = []

for _ in range(m):
    x, y = map(int, input().split())
    
    array[x].append(y) # x → y
    indegree[y] += 1

for i in range(1, n + 1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)

result = []
while heap:
    data = heapq.heappop(heap)
    result.append(data) # 큐에서 나온 순서대로
    
    for y in array[data]:
        indegree[y] -= 1

        if indegree[y] == 0:
            heapq.heappush(heap, y) # 항상 맨 앞의 원소가 최소값 -> 난이도가 낮은 것부터 풀기 위해

for i in result:
    print(i, end=' ')