백준 20119 클레어와 물약(python)

문제

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

20119번: 클레어와 물약

---

문제에서 느꼈던 중요한 포인트는 물약을 만들 수 있는 레시피가 여러 개 존재할 수 있다는 점이었습니다.

만들 수 있는 레시피들의 포션의 존재 여부를 파악하면서 해당되는 레시피가 하나라도 완료되면 포션을 만들 수 있기 때문에 결과에 넣어주었습니다. 과정은 다음과 같습니다.

• 물약 데이터 클래스를 만들어서 연결될 점들과 레시피들, 필요한 포션의 개수들,  만들 수 있는지 여부를 기록합니다.
• 주어진 기존에 가지고 있는 포션들의 정보들을 포션 클래스로 저장해주고, 큐에 넣어줍니다.
• 큐에서 나온 현재 물약과 연결된 물약들을 확인합니다. 연결된 물약의 레시피들을 돌아보면서 현재 물약과 연결되어 있으면 체크해주고 차수를 빼줍니다.
• 만약 그 레시피의 차수가 0이 된다면 다 연결된 것이므로 결과 값에 추가해 줍니다.

포션 간의 관계를 저장하는데 필요한 정보들을 정리하는데 시간이 걸렸던 것 같습니다.

---

소스코드 

import sys
from dataclasses import dataclass, field
from collections import deque
from typing import List

# 물약 데이터 클래스
@dataclass
class Potion:
    number: int = None
    connect: List[int] = field(default_factory=list)
    recipe: List[int] = field(default_factory=list)
    indegree: List[int] = field(default_factory=list)
    flag: bool = False


input = sys.stdin.readline

N, M = map(int, input().split())
res = []
potion_list = [Potion() for _ in range(0, N+1)]


for i in range(M):
    k, *x, r = map(int, input().split())
    for j in x:
        potion_list[j].connect.append(r)
# 포션 레시피 들을 추가해주고 그에 맞게 진입 차수도 저장해 줍니다.
    potion_list[r].recipe.append(x)
    potion_list[r].indegree.append(len(x))


L = int(input())

# 기존에 가지고 있는 포션 처리
in_ = map(int, input().split())
for ele in in_:
    potion_list[ele].flag = True
    potion_list[ele].number = ele
    res.append(ele)

q = deque()

for i in res:
    q.append(potion_list[i])

while q:
    tmp = q.popleft()
    cur_number = tmp.number
    #현재 포션과 연결된 포션들을 탐색합니다
    for i in tmp.connect:
        next = i
        if potion_list[next].flag == True:
            continue
        for j in range(len(potion_list[next].recipe)):
            if potion_list[next].flag:
                break
            for k in range(len(potion_list[next].recipe[j])):
                if cur_number == potion_list[next].recipe[j][k]: #탐색하는 레시피에 가지고 있는 포션이 있다면 레시피의 차수를 줄여줍니다.
                    potion_list[next].recipe[j][k] = -1
                    potion_list[next].indegree[j] -= 1
                    if potion_list[next].indegree[j] == 0: #레시피의 포션들이 다 존재 한다면 포션을 체크해 줍니다.
                        potion_list[next].flag = True
                        break

        if potion_list[next].flag:
            res.append(next) 
            potion_list[next].number = next
            q.append(potion_list[next])


res.sort()
print(len(res))
print(*res, end=" ")