[BOJ/Python] 23059_리그 오브 레게노

문제 출처:https://www.acmicpc.net/problem/23059

23059번: 리그 오브 레게노

문제

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

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

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

 

입력

첫째 줄에는 백남이가 알고 있는 아이템 사이의 관계의 수 N(1 ≤ N ≤ 200,000)를 입력받는다. N개의 줄에 걸쳐서 아이템 이름을 의미하는 문자열 2개 A B가 주어진다. 아이템 A는 아이템 B를 구입하기 위해 앞서 구매해야 하는 것을 의미하며, 아이템 A와 아이템 B는 항상 다르다. 모든 아이템은 선후관계에서 적어도 한 번씩 등장한다. 아이템 이름은 알파벳 소문자로만 이루어져 있고, 공백을 포함하지 않는다. 아이템 이름의 길이는 1 이상 15 이하이다.

출력

먼저 구매해야 하는 아이템부터 순서대로 각 줄에 걸쳐서 출력하라. 단, 모든 아이템을 구매할 수 없다면 -1을 출력한다.

예제 입력 1

4
galeforce everfrost
riftmaker everfrost
goredrinker galeforce
stridebreaker galeforce

예제 출력 1

goredrinker
riftmaker
stridebreaker
galeforce
everfrost

예제 입력 2

2
riftmaker galeforce
galeforce riftmaker

예제 출력 2

-1

예제 입력 3

2
goredrinker galeforce
riftmaker everfrost

예제 출력 3

goredrinker
riftmaker
everfrost
galeforce

---

풀이

 

위상정렬 문제이다.

A B 가 주어졌을 때, B는 A를 구입한 이후에 구매할 수 있는 아이템이다.

만약 A B, C B 인 경우, B는 A와 C를 모두 구매한 이후에 구입할 수 있다.

 

1. 현재 구매할 수 있는 아이템들을 사전순으로 모두 구입한다.
2. 아이템들을 구매하고 나면, 추가로 구매할 수 있는 아이템들이 생긴다.
3. 1~2의 과정을 반복한다.

코드는 다음과 같다.

 

import sys
import heapq
 
def topological_sort():
    queue = []
    next_queue = []
    result = []
    for key,value in indegree.items():
        if value==0:
            heapq.heappush(queue,key)
 
    while queue:
        item = heapq.heappop(queue)
        result.append(item)
 
        for next in graph[item]:
            indegree[next]-=1
            if indegree[next]==0:
                heapq.heappush(next_queue,next)
        
        if len(queue)==0:
            queue = next_queue
            next_queue=[]
 
    if len(result)!=len(indegree):
        print(-1)
    else:    
        print(*result,sep='\n')
 
 
n = int(sys.stdin.readline())
indegree = dict()
graph = dict()
 
for _ in range(n):
    a,b = sys.stdin.readline().split()
    if a not in indegree:
        indegree[a] = 0
    if b not in indegree:
        indegree[b] = 0
    
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
 
    graph[a].append(b)
    indegree[b]+=1
 
topological_sort()

1. indegree를 통해 해당 아이템의 진입차수를 나타내었고, graph를 통해 해당 아이템을 구매하고 난 뒤에 구매할 수 있는 아이템들을 표현하였다.
2. heapq 모듈을 이용하여 우선순위 큐 queue와 next_queue를 만들었다.
3. 둘을 분리한 이유는 현재 시점에서 구매할 수 있는 아이템들을 사전순으로 모두 구매한 이후에 추가로 생성된 구매할 수 있는 아이템들을 구매하기 때문에, 현재 시점에서 구매할 수 있는 아이템들인 queue의 원소들을 다 구매한 후에 next_queue의 원소들을 구매하도록 구현하였다.
4. 만약 구매한 아이템의 개수가 아이템의 개수와 다르다면, 구매하지 못한 아이템이 존재하므로 -1을 출력하고, 아니라면 구매한 아이템들을 순서대로 출력한다.