백준 1766 문제집 문제풀이

문제 

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

1766번: 문제집

 

 

문제 접근 방식

문제들 간에 의존성이 존재하기 때문에 위상정렬 알고리즘을 사용해야겠다고 판단했다. 기존 위상정렬 문제와는 다르게, 진입차수가 0인것이 여러개 있는 경우 쉬운 문제(숫자가 낮은 문제)부터 풀어야한다. 큐에 여러 문제가 있을 때 낮은 숫자의 문제를 먼저 선택해서 풀면 되기 떄문에 기존 큐를 우선순위 큐로 변경하여 문제를 풀었다.

 

 

시간 복잡도

우선 순위 큐를 사용하여 N의 노드를 순회하는데 O(NlogN) 이 걸리며, 간선을 모두 순회하는데 O(M) 가 걸린다. 전체적인 시간복잡도는 O(NlogN+M)가 되며, N의 최댓값은 32000,  M의 최댓값은 1e5 이므로 시간내에 동작한다.

 

 

코드

import sys
import heapq

input = sys.stdin.readline

if __name__ == '__main__':
    n, m = map(int, input().split())
    in_degree = [0] * (n + 1)
    adj = [[] for _ in range(n + 1)]

    # 인접리스트 & 진입차수 초기화
    for _ in range(m):
        a, b = map(int, input().split())
        adj[a].append(b)
        in_degree[b] += 1

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

    # 우선순위 큐를 순회하며 위상정렬을 실행한다.
    answer = []
    while pq:
        # 우선순위 큐에 있는 노드 중 가장 작은 노드(쉬운 문제)를 꺼내고, answer에 추가한다.
        now = heapq.heappop(pq)
        answer.append(str(now))

        #인접한 노드를 순회하며 진입차수를 1 감소시키고, 진입차수가 0인 것을 우선순위 큐에 넣어준다.
        for next in adj[now]:
            in_degree[next] -= 1

            if in_degree[next] == 0:
                heapq.heappush(pq, next)

    print(' '.join(answer))

 

 

회고

위상 정렬에서 문제 유형에 따라 우선순위 큐를 활용할 수 있다는 것을 경험했다.