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

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

23059번: 리그 오브 레게노

1. 아이템의 일부 구매 순서로 전체 구매 순서를 찾는다 => 위상정렬

2. 이때, 구매 과정이 현재 구매가능한 아이템을 모두 "찾기만 하고" 그 결과를 이름 순대로 구매한다.

이 점만 주의하면 된다.

 

나는 아이템은 맵으로 관리하고 우선순위큐와 위상정렬을 섞어서 풀었다.

 

<알고리즘>

1. 맵에 저장한 아이템에 대해 위상정렬 한다.
2. 현재 살 수 있는 아이템 리스트를 만든다. 만들면서 정답 리스트에 아이템을 추가한다.
3. 해당 리스트를 우선순위큐 리스트로 만든다. (heapify)
4. 리스트에서 아이템을 하나씩 뽑으면서 다음 아이템 리스트를 만든다.
5. 3번 과정으로 돌아가서 리스트를 만들 수 없을 때까지 반복
6. 정답리스트의 요소 개수가 전체아이템 개수와 같다면 순서 출력, 아니면 -1 출력

from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.readline

n = int(input())
items = dict()
for _ in range(n):
    i1, i2 = input().split()
    try:
        items[i1]["list"].append(i2)
    except:
        items[i1] = dict()
        items[i1]["list"] = [i2]
        items[i1]["count"] = 0

    try:
        items[i2]["count"] += 1
    except:
        items[i2] = dict()
        items[i2]["list"] = []
        items[i2]["count"] = 1

pq, answer = [], []
itemCount = len(items)

for key in items.keys():
    if items[key]["count"] == 0:
        heappush(pq, key)

while True:
    next_list = []
    while pq:
        key = heappop(pq)
        for conn_item in items[key]["list"]:
            items[conn_item]["count"] -= 1
            if items[conn_item]["count"] == 0:
                next_list.append(conn_item)

        answer.append(key)
    if not next_list:
        break

    heapify(next_list)
    pq = next_list

if len(answer) == itemCount:
    for ans in answer:
        print(ans)
else:
    print(-1)

근데 굳이 우선순위큐를 써야했을까?

(사실 아이템 뽑고, 진입차수 갱신한다음 바로 진입차수가 0인 아이템을 넣어주려고 우선순위 큐를 썼었는데,

그게 문제가 된 이상 더이상 우선순위 큐를 쓸 필요가 없었다.

 

import sys
input = sys.stdin.readline

n = int(input())
items = dict()
for _ in range(n):
    i1, i2 = input().split()
    try:
        items[i1]["list"].append(i2)
    except:
        items[i1] = dict()
        items[i1]["list"] = [i2]
        items[i1]["count"] = 0

    try:
        items[i2]["count"] += 1
    except:
        items[i2] = dict()
        items[i2]["list"] = []
        items[i2]["count"] = 1

buy_list, answer = [], []

for key in items.keys():
    if items[key]["count"] == 0:
        buy_list.append(key)
buy_list.sort()

while True:
    next_list = []
    for key in buy_list:
        for conn_item in items[key]["list"]:
            items[conn_item]["count"] -= 1
            if items[conn_item]["count"] == 0:
                next_list.append(conn_item)

        answer.append(key)
    if not next_list:
        break

    buy_list = next_list
    buy_list.sort()

if len(answer) == len(items):
    for ans in answer:
        print(ans)
else:
    print(-1)

 그냥 정렬했다.

 

더 빨라졌다(...)

 

import sys
input = sys.stdin.readline

n = int(input())
items = dict()
for _ in range(n):
    i1, i2 = input().split()
    try:
        items[i1]["list"].append(i2)
    except:
        items[i1] = dict()
        items[i1]["list"] = [i2]
        items[i1]["count"] = 0

    try:
        items[i2]["count"] += 1
    except:
        items[i2] = dict()
        items[i2]["list"] = []
        items[i2]["count"] = 1

buy_list, answer = [], []

for key in items.keys():
    if items[key]["count"] == 0:
        buy_list.append(key)

while buy_list:
    next_list = []
    for key in sorted(buy_list):
        for conn_item in items[key]["list"]:
            items[conn_item]["count"] -= 1
            if items[conn_item]["count"] == 0:
                next_list.append(conn_item)
        answer.append(key)

    buy_list = next_list

if len(answer) == len(items):
    for ans in answer:
        print(ans)
else:
    print(-1)

중복된 코드를 없애고 코드를 조금 정리했다.