백준 우선순위 큐 1766번

안녕하세요 GDSC ML 멤버 나건주입니다.
파이썬 알고리즘 스터디 6번째 주제 우선순위 큐의 두번째 문제를 풀어보았습니다.

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

해당 문제는 우선순위 큐, 그래프 이론, 위상 정렬 이렇게 알고리즘 분류된 문제였습니다.

우선순위 큐는 앞에 문제들을 풀면서 어느정도 감이 왔지만 위상 정렬이라는 개념을 잘 알지 못해서 찾아보았습니다.

우선순위 큐란?

우선순위 큐는 힙이라는 자료구조와 같습니다.
파이썬에서는 heapq라는 모듈을 지원해주는데 모듈에 있는 함수는 다음과 같습니다.

heapq.heappush(a,b): b를 a에 추가 - O(logn)
heapq.heappop(a): a에서 가장 작은 원소를 pop한 다음 리턴해주며 비어있으면 IndexError 발생 - O(logn)
heqpq.heapify(a): 리스트 a를 즉각적으로 heap으로 변환 - O(n) -> 만약 heappush로 만든다면? O(nlog(n))
하지만 heapify는 최소 힙만을 지원합니다.

최소 힙이란 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 말합니다.
최대 힙이란 각 노드의 키 값이 자식의 키 값보다 작지 않은 트리입니다.

위상 정렬이란?

‘순서가 정해져 있는 작업’을 차례로 수행해야 할 때, 순서를 결정할 때 사용하는 알고리즘입니다.
방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으며 모든 정점을 나열하면 됩니다.
하나의 방향 그래프에는 여러 개의 위상 정렬이 가능합니다.
또한 위상 정렬에는 사이클이 존재하면 안된다고 합니다.

문제 풀이

위상 정렬을 만들기 위해 problem_list를 이중 리스트로 표현하는 것이 여러개의 우선 순위를 저장하기 좋다고 합니다.
3개의 리스트를 만들어서 우선순위 존재 여부 확인, 우선순위에 있는 숫자들을 분리, 결과값 저장에 각각 사용하는 것이 나중에 원하는 값을 추출하기 편했습니다.

import heapq

problem, compare = map(int, input().split())
problem_list = [[] for i in range(problem + 1)] # 위상정렬 표현 ,index가 헷갈리지 않게 problem+1
pre = [0 for i in range(problem + 1)] #1: 우선순위가 있다.
heap = [] # 먼저 풀 문제들을 저장
result = [] # 결과값을 저장

for i in range(compare):
    a, b = map(int, input().split())
    problem_list[a].append(b) # 위상 정렬 만들기
    pre[b] += 1 #우선순위가 있다면 +1
    
print(problem_list)
print(pre)

4 2
4 2
3 1
[[], [], [], [1], [2]]
[0, 1, 1, 0, 0]


for i in range(1, problem + 1):
    if pre[i] == 0: #우선순위가 없는 것 먼저 heap에 push
        heapq.heappush(heap, i) 

while heap: # heap에 남은 것이 없을 때까지
    temp = heapq.heappop(heap) # 우선순위중 가장 작은 것 먼저 추출
    result.append(temp) 
    for j in problem_list[temp]: # 위상 정렬 만든 것에서  확인
        pre[j] -= 1 # 우선순위가 1인 것을 0으로 만들어줌-> 더이상 우선순위가 없다는 의미
        if pre[j] == 0: #우선순위가 더이상 없는 제일 작은 수를 push해줌
            heapq.heappush(heap, j)

for i in result: # 결과값 출력
    print(i, end=' ')

3 1 4 2

처음에 어떻게 접근해야할지 감을 잡지 못해서 위상 정렬도 찾아보고 그래프 이론도 찾아보았습니다.
조건에 맞는 값들을 쉽게 찾기 위해 잘 분리해내는 것이 좀 문제를 파악하기 좋은 것 같습니다.

이번주 문제는 다들 어려운 것 같네요.. ㅠ