23632 쿠키런 킹덤

고오급 알고리즘 스터디 - 5

풀이

• 단순하게 공장끼리 연결하는 것은 해결 불가능
• 어떻게 그래프를 연결해야 할까?
• 공장 : 생산 자원 / 필요 자원
  • 필요 자원의 개수 : 전입 차수
  • 생산 자원의 개수 : 전출 차수
• 자원을 만드는 데에는 0초가 걸린다 : 생산이 가능한 자원은 무제한으로 사용 가능하다.

1. 건설 완료된 공장에서 자원을 생산
2. 기존에 생산된 자원이 아니라면 해당 자원을 건설에 필요로 하는 공장에 전달
3. 공장 생산에 필요한 자원을 모두 받았다면 건설 시작
4. 1-3 과정을 주어진 시간 T초 동안 반복

import sys
from collections import deque

n, m, t = map(int, sys.stdin.readline().split())
already_create = list(map(int, sys.stdin.readline().split()))
create = [[] for _ in range(n+1)]
for i in range(1, n+1):
    create[i] = list(map(int, sys.stdin.readline().split()))[1:]

resource = [False] * (n+1)
resource_graph = [[] for _ in range(n+1)]
factory_indegree = [0] * (n+1)

for _ in range(n-m):
    input_data = list(map(int, sys.stdin.readline().split()))
    index = input_data[0]
    need_resource = input_data[2:]
    for r in need_resource:
        resource_graph[r].append(index)
        factory_indegree[index] += 1

res = []
queue = deque()
for a in already_create:
    queue.append((a, 0))

while queue:
    num, time = queue.popleft()
    if time <= t:
        res.append(num)

    for c in create[num]:
        if not resource[c]:
            resource[c] = True
            for f in resource_graph[c]:
                factory_indegree[f] -= 1
                if factory_indegree[f] == 0:
                    queue.append((f, time+1))

res.sort()
sys.stdout.write(str(len(res)) + '\n')
print(*res)

23632 쿠키런 킹덤