[클레어와 물약/G1/Python3]

20119번 클레어와 물약 G1

 

문제
세상에는 N종류의 물약이 있고 클레어는 M개의 레시피를 알고 있다. 레시피는 (x1, x2,..., xk) → r 형태로 표현할 수 있고 x1번, x2번 ..., xk번 물약을 모두 섞어서 r번 물약을 만들 수 있다는 뜻이다.현재 클레어에게는 y1번, y2번, ..., yL번 물약만 있다. 만들 수 있는 물약들을 전부 알아내주자. 클레어가 가지고 있는 각 종류의 물약의 양은 무한대라고 가정하자.

입력
첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000)과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다. 다음 M개의 줄에는 각각의 줄마다 레시피의 정보 ki, xi1, xi2,..., xiki, ri (1 ≤ ki < N, 1 ≤ xij, ri ≤ N, xij ≠ ri)가 주어지며 이는 (xi1, xi2,..., xiki) → ri 형태의 레시피를 의미한다.M+2 번째 줄에는 현재 클레어가 가지고 있는 물약 종류의 수 L (1 ≤ L < N) 이 주어진다.M+3 번째 줄에는 y1, y2,..., yL (1 ≤ yi ≤ N) 이 주어진다.모든 ki의 합은 400,000을 넘지 않는다.

출력
첫 번째 줄에 클레어가 만들 수 있는 물약의 개수를 출력한다.
두 번째 줄에는 만들 수 있는 물약의 번호를 오름차순으로 출력한다.

 

그래프 이론, 그래프 탐색, 위상 정렬, 방향 비순환 그래프

 

위상 정렬 알고리즘으로 풀이를 진행했다. 

여러 레시피 중 하나라도 가능하면 물약 제조가 가능하다는 점이 있다.

문제 해결을 위해 레시피를 대상으로 위상 정렬을 진행했다.

각 레시피로 만들어지는 물약이 어떤 것인지 알기 위해, 각 레시피의 최종 결과를 담는 변수도 제작했다.

 

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
routes = [[] for _ in range(n+1)] # using num
done = [False] * (n+1) # using num
cnts = [0] * (n+1) # using index
p = [0] * (n+1) # using index

for t in range(m):
    recipe = list(map(int, sys.stdin.readline().split()))
    need_num = recipe[0]
    cnts[t] = need_num
    p[t] = recipe[-1]
    for i in range(1, need_num+1):
        routes[recipe[i]].append(t)

know = int(sys.stdin.readline())

result = list(map(int, sys.stdin.readline().split()))
dq = deque()
for v in result:
    done[v] = True
    dq.append(v)

while dq:
    v = dq.popleft()
    for i in routes[v]:
        cnts[i] -= 1
        if cnts[i] == 0 and not done[p[i]]:
            dq.append(p[i])
            result.append(p[i])
            done[p[i]] = True

print(len(result))
result.sort()
for v in result:
    print(v, end=' ')

 

---

 

레시피를 기준으로 위상 정렬한다는 아이디어로 인해 다른 위상 정렬 문제에 비해 난이도가 높게 평가가 되어있다.