[ 백준 / G2 / 파이썬 Python ] 리그 오브 레게노

링크 : https://www.acmicpc.net/problem/23059

23059번: 리그 오브 레게노

 

코드

---

from collections import defaultdict
from heapq import heappop,heappush

n = int(input())
item = defaultdict(list) # a를 사면 b를 살 수 있다.
depth = defaultdict(int)
allItem = set()

for _ in range(n):
    a,b = input().split()
    allItem.update({a,b})
    item[a].append(b)
    depth[b] += 1

zeroDepth = []
for x in allItem :
    if depth[x] == 0:
        heappush(zeroDepth,x)

popedItem, tmp = [],[]
while zeroDepth:
    popedItem.append(node := heappop(zeroDepth))
    for nextNode in sorted(item[node]):
        depth[nextNode] -= 1
        if depth[nextNode] == 0:
            heappush(tmp,nextNode)
    if not zeroDepth:
        if not tmp: break
        zeroDepth = tmp
        tmp = []

if len(popedItem) != len(allItem):
    print(-1)
else:
    for x in popedItem:
        print(x)

 

사용 알고리즘

---

" 위상-정렬 + 우선순위큐 "

 

풀이

---

이 문제의 핵심은 딱 두가지이다.

1. 아이템 사이에는 미리 정해진 순서가 존재한다.
2. 현재 구매할 수 있는 아이템 중 아직 구매하지 않은 아이템을 '모두' 찾고 그 아이템들을 사전순으로 '모두' 구매한다.

1번 조건은 단순한 위상-정렬 알고리즘으로 충분히 해결이 가능하다. 하지만 여기서 문제가 되는 점은 2번이다.

현재 구매할 수 있는 아이템을 모두 찾는다는 말은 먼저 구매해야 할 아이템이 이미 모두 구입된 아이템들을 찾는다는 말이고, 사전순으로 모두 구매한다는 말은 그 아이템들을 정렬하여 그 순서대로 모두 구매해야 한다는 것이다.

 

만약 구매할 수 있는 아이템을 찾을 때마다 모두 사전순으로 정렬하게 된다면 시간복잡도가 크게 올라갈 것이다. 따라서 우선순위큐를 사용했다.

while zeroDepth:
    popedItem.append(node := heappop(zeroDepth))
    for nextNode in sorted(item[node]):
        depth[nextNode] -= 1
        if depth[nextNode] == 0:
            heappush(tmp,nextNode)
    if not zeroDepth:
        if not tmp: break
        zeroDepth = tmp
        tmp = []

먼저 구매할 수 있는 아이템들을 모두 찾고 사전순으로 하나씩 탐색하였다. 해당 아이템을 구매함으로써 구매가 가능해진 아이템의 목록을 따로 저장하고 이전에 찾은 아이템을 모두 사용하기 위해서 구매할 수 있는 아이템이더라도 이전 아이템 목록을 모두 구매한 뒤 새로 추가하였다.