[백준] 1766 문제집 (Python/파이썬)

<문제 링크>

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

1766번: 문제집

<풀이 전략>

1. 우선순위큐로 위상정렬을 수행하면 되는 문제이다.

2. 문제의 조건을 읽어보면 비교적 명확하다.

- 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. ->  위상정렬

- 가능하면 쉬운 문제부터 풀어야 한다. -> 우선순위 큐

3. 위상정렬 공부하면서 푼 문제였는데 위상정렬임을 알고 풀어서 그런지 몰라도 난이도에 비해서 쉬웠다.

 

<정답 코드>

import heapq
import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 221003 1766 문제집

# 정답코드

# N: 문제의 수, M: 정보의 수
N, M = map(int, input().split())

# indegree: 진입차수, graph: 그래프로 나타낸 문제들의 선후 관계
indegree = [0 for _ in range(N + 1)]
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    indegree[node2] += 1

# reuslt: 결과를 담을 리스트, queue: 위상정렬 시 사용할 배열(우선순위큐)
result = []
queue = []

# 진입차수가 0인 문제들을 우선순위큐에 넣어준다.
for i in range(1, N + 1):
    if indegree[i] == 0:
        heapq.heappush(queue, i)

# 우선순위큐(쉬운문제 우선)를 이용하여 위상정렬을 수행한다.
while queue:
    current = heapq.heappop(queue)
    result.append(current)

    for next in graph[current]:
        indegree[next] -= 1
        if indegree[next] == 0:
            heapq.heappush(queue, next)

# 결과 출력
print(*result)