백준 1766 - 문제집 (Python)

https://acmicpc.net/problem/1766 

1766번: 문제집

위상 정렬의 개념을 모르고 풀어서 한참을 고생한 문제였다.

처음 풀이는 이랬다.

import sys, heapq
from collections import deque
input=sys.stdin.readline
n,m=map(int,input().split())
ps=[]
visited=[False]*(n+1)
for _ in range(m):
    heapq.heappush(ps,deque(list(map(int,input().split()))))

while ps:
    cur=heapq.heappop(ps)
    if cur:
        temp=cur.popleft()
        if not visited[temp]:
            print(temp,end=" ")
            visited[temp]=True
        if cur:
            heapq.heappush(ps,cur)

즉 단순히 생각해서 먼저 풀어야 하는 문제와 후에 풀어야 하는 문제의 리스트를 만들고, heap을 이용해 먼저 풀어야 하는 문제의 번호가 낮을수록 먼저 빼준다는 생각이었으나, 이런 방식으로는 문제를 풀 수 없어 위상정렬을 공부했다.

 

위상정렬은 사이클이 없는 그래프에서만 가능한 정렬로, 딱 이 문제처럼 어떤 노드를 방문하기 위해서 그 전 노드를 탐색해야만 하는 경우 적용하는 방법이다.

 

골자는 굉장히 간단한데, 이 문제 식대로 해석하자면 다음과 같다.

우선 선수과목과 후순위 과목을 입력받아 후순위 과목의 우선순위에 +1을 하는 식으로 노드를 정리한다.

그 후, 선수과목이 없는 과목들로 heap을 만들고,

1. heap에서 요소를 pop한다.

2. 그 문제를 선수과목으로 하는 과목들의 우선순위에 -1을 해준다.

3. 우선 순위가 0이 된 문제는 heap에 push 한다.

이 과정을 반복해주면 된다.

 

이때 '우선순위'를 우리는 진입 차수(in-degree)라고 한다.

이렇게 작성한 코드는 다음과 같다.

import heapq
num_problem, num_compare = map(int, input().split())
problem_list = [[] for i in range(num_problem + 1)]
indegree = [0 for i in range(num_problem + 1)]
heap = []
result = []


for i in range(num_compare):
    first, next = map(int, input().split())
    problem_list[first].append(next) #선수과목과 후순위 과목 사이 간선을 만든다.
    indegree[next] += 1 #후순위 과목의 진입 차수를 올린다.


for i in range(1, num_problem + 1):
    if indegree[i] == 0:
        heapq.heappush(heap, i) #진입 차수가 0인 과목을 heap에 넣고

while heap: #heap 내에 과목이 있는 동안
    temp = heapq.heappop(heap) #가장 과목 번호 수가 적은 것을 pop한다.
    result.append(temp)
    for j in problem_list[temp]: #만들어두었던 선수과목-후순위 과목 그래프를 돌며
        indegree[j] -= 1 #후순위 과목의 진입차수를 줄이고
        if indegree[j] == 0: #진입 차수가 0이면
            heapq.heappush(heap, j) #그 과목 또한 heap에 넣어준다.

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

새로웠고, 여러 모로 쓸 곳이 있겠다는 생각이 든 개념이었다.