문제집

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

1766번: 문제집

문제요약:

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

문제번호가 작을 수록 쉬운 문제이고 m개의 문제간의 우선순위(먼저 푸는것이 좋음) 이 주어질 때 문제를 풀어야하는 순서를 출력하시오.

 

난이도:

골드2

 

소요시간:

15분

 

제출횟수:

1회

 

코딩:

import heapq as hp
n,m = map(int,input().split())
graph =[[] for _ in range(n+1)]
indegree = [0]*(n+1)
for _ in range(m):
    s,e = map(int,input().split())
    graph[s].append(e)
    indegree[e] +=1
    
q = []
for i in range(1,n+1):
    if indegree[i] == 0 :
        hp.heappush(q,i)


result = []
while q:
    i = hp.heappop(q)
    result.append(i)
    for j in graph[i]:
        indegree[j]-=1
        if indegree[j] == 0:
            hp.heappush(q,j)

print(*result)

사실 어떤식으로 풀어야할지에 대한 고민을 오래 하고 이렇게 풀어야한다는 것을 안 뒤에 구현은 금방했던 문제입니다. 

기본적으로는 작은숫자들을 우선적으로 풀어야 하지만 숫자들간에 우선순위가 있기 때문에 처음에는 무조건 두 그룹으로 나눠서 풀어야하나 생각했습니다. 하지만 n보다 m의 범위가 더 크고, 숫자가 중복해서 존재하지 않는다는 말이 없기 때문에 우선순위에서 나오는 숫자들은 중복이 되어 나올 수 있고 어떤숫자는 어떤숫자보다는 빨라야하지만 어떤숫자보다는 느려야 할 수 있습니다. 이것을 인지한 뒤엔 무조건 그래프로 풀어야 겠다는 생각이 들었고, 이후 indegree를 활용한 위상정렬로 풀어야 겠다는 생각을 했습니다. 그래서 indegree를 설정해준뒤 하나씩 빼주면서 0이 되는 것을 넣어주었는데 이때, 그냥 위상정렬처럼 deque에 넣는것이 아닌 heap(우선순위 큐)에 넣음으로써 우선순위를 만족하면서 그중에서 가장 작은 숫자가 (두번째 우선순위) 우선으로 나오게 설정해 주었습니다.