[백준] (23059) 리그 오브 레게노 [Python]

문제 링크

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

문제

백남이는 새 학기를 맞이하여, 리그 오브 레게노(League of Legeno)라는 게임을 시작했다. 리그 오브 레게노는 AOS(Aeon of Strife) 종류의 게임으로, 5명의 플레이어가 한 팀이 되어 상대편의 주요 건물을 부수는 것이 게임의 승리 목표이다. 게임 내에서 유저들은 게임에서 승리하기 위해 자신의 캐릭터의 능력치를 올리도록 해야 한다. 맵에 등장하는 몬스터나 상대 팀의 플레이어를 처치하며 경험치와 골드를 보상으로 얻고, 이 경험치를 통해 캐릭터의 레벨을 올림으로써 레벨 증가에 따른 능력치를 얻게 된다. 그러나 한 게임에서 레벨에 대한 일정 상한선이 존재한다. 다른 방법으로는 골드를 사용하여 아이템들을 구매함으로써 자신의 능력치를 높일 수 있다.

아이템 사이에 미리 정해진 구매 순서가 존재한다. 이제 막 게임을 시작한 백남이는 구매 순서 전체가 아니라 두 아이템 사이의 선후관계 일부만 알고 있다. 백남이가 다음 과정을 반복하여 아이템을 구매할 때, 아이템의 전체 구매 순서를 알아내자.

• 현재 구매할 수 있는 아이템 중 아직 구매하지 않은 아이템을 모두 찾는다.
• 찾은 아이템을 사전 순으로 모두 구매한다.

코드

from collections import defaultdict
from heapq import heappush, heappop

n = int(input())
d = defaultdict(int)
items = defaultdict(list)
all_items = set()

for _ in range(n):
    a, b = input().split()
    items[a].append(b)
    d[b] += 1
    all_items.add(a)
    all_items.add(b)

queue = list()
for item in all_items:
    if d[item] == 0:
        heappush(queue, item)

result = list()
tmp = list()
while queue:
    item = heappop(queue)
    result.append(item)
    for next_item in items[item]:
        d[next_item] -= 1
        if d[next_item] == 0:
            heappush(tmp, next_item)
    if not queue:
        if not tmp:
            break
        queue = tmp
        tmp = list()

if len(result) == len(all_items):
    for item in result:
        print(item)
else:
    print(-1)

해설

위상 정렬 알고리즘을 활용해서 푸는 문제다.

[WEEK03] 위상 정렬