[백준] 문제집 : 1766 Python

이 문제는 백준 키순서에 내가 적어놓은 예시와 거의 유사한 문제였다.  문제집 커리큘럼에 따라 한 문제를 풀기 위해서는 선행되어야 하는 문제(진입 차수)가 있고, 이 문제는 그 순서대로 문제를 풀 때 어떤 순서대로 풀어야 할지를 묻는 문제이다. 

여기서 하나의 추가조건이 있는데 가능하다면 쉬운 문제 (인덱스가 작은 문제)를 먼저 풀어야 한다. 나는 이 부분에서 조금 헷갈렸는데 이 문제가 원하는 것은 2번 문제(선행 문제가 1인 문제)와 3번 문제(선행 문제가 없는 문제)가 있다면 1-2-3 순서로 문제를 풀어야 한다. 즉, 선행 문제가 있다 하더라도 문제의 난이도는 인덱스가 결정한다.

위상 정렬과 문제만 이해했다면, 쉽게 풀 수 있을 것이다. 우리에게는 자동으로 인덱스를 정렬해주는 힙이라는 무기가 있기 때문이다.

나의 아이디어를 정의하자면 아래와 같다.
1. 위상 정렬을 통해 차수가 낮은 문제부터 힙 자료구조에 담는다.
2. 힙 자료구조는 자동으로 내가 풀 수 있는 문제 중 인덱스가 작은 것부터 꺼내 줄 것이기 때문에 이대로 답을 제출한다. 

이를 코드로 나타낸다면 아래와 같다.

from sys import stdin
from heapq import heappop, heappush

input = stdin.readline

N, M = map(int,input().split())

#. 1 방향 그래프, 진입차수 만들기
arr = [[] for _ in range(1+N)]
inD = [0] * (N+1)

for _ in range(M):
    s, e = map(int,input().split())
    arr[s].append(e)
    inD[e] += 1


# 2. 진입차수가 0인것 부터 큐에 넣기
Q = []
for idx in range(1,N+1):
    if not inD[idx]:
        heappush(Q,idx)

# 3. Q(힙자료구조)를 통한 위상정렬
answer = []

while Q:
    now = heappop(Q)
    answer.append(now)
    ## 3-1 Q에서 하나씩 제거하면서 정답기록 및 연결된 노드들의 진입차수 줄이기
    for i in arr[now]:
        inD[i] -= 1
    ## 3-2. 진입차수가 0이 된 문제들 Q에 담기
        if inD[i] == 0:
            heappush(Q, i)

print(*answer)

문제를 이해하는 과정에서 손 코딩을 하지 않아 힙 자료구조 대신 2차원 배열을 이용하여 난이도를 구분하려고 시도를 했어서 시간을 많이 소모하였다. 문제를 봤을 때 내가 아는 알고리즘에 관한 문제여도 문제를 정확하게 이해하기 전에 코드를 짜는 습관을 지양해야겠다.