백준 2637_장난감조립

장난감조립(백준 2637)

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

아이디어의 접근은 나쁘지 않았으나,
‘메모리 초과’가 발생하여
queue의 append 횟수를 줄이는 방법을
고려하였다

Code

import sys
from collections import deque

inp = sys.stdin.readline

# '우선순위'가 필요하며
# 필요한 '기본 부품'이 완제품을 만들기 위해 '얼마나'필요한가 에 대한 것
# 위상정렬
# 서로를 필요로 하는 경우는 없음 (scc X)

# 약간 top-down 방식으로 해보려고 함
# 위에서 미리 필요 개수를 정한뒤
# 해당 재료에 '자식'들이 있다면 그 수치를 유지한채 
# answer의 배열에 더해줄 예정
# 자식이 없다면 '기초'재료

num = int(inp().strip())
needs = int(inp().strip())
graph = [[] for _ in range(num)] # 그래프
answer = [0 for _ in range(num)] # 필요한 재료 인덱스에 answer 넣어주려 한다

que = deque()

#필요한 재료 공급받기
for i in range(needs):
    tar, need, count = map(int,inp().split()) # 만들것, 필요한 것, 필요한 수
    graph[tar - 1].append([need - 1, count]) # 해당 필요 요소 집어넣기

basic = []

for i in range(len(graph)):
    if len(graph[i]) == 0:
        basic.append(i)

que.append([num - 1,1])

# 필요한 재료를 넣어주기
while que:
    tar, needCount = que.popleft()
    
    for need, needC in graph[tar]:
        if need in basic: # 필요한 재료가 기본재료다
            answer[need] += needC * needCount
        else:
            find = False
            for i in range(len(que)):
                if que[i][0] == need:
                    que[i][1] += needC * needCount
                    find = True
                    break

            if find == False:
                que.append([need, needC * needCount])
    

for i in range(num):
    if answer[i] != 0:
        print(f'{i + 1} {answer[i]}')

해결 아이디어

1. top-down 방식의 분할정복으로 가능하지 않을까?
2. 받은 데이터를 ‘그래프’에 저장하되,
   그래프의 해당 인덱스가 비어있다면 ‘기본 재료’취급
   
3. ‘완제품’의 index(num - 1)와 필요개수(1)을
   queue에 넣어준다
4. while문을 돌며, 각 요소의 ‘필요 재료’를 확인하고
   ‘기본 재료’라면 answer에 넣어준다.
   그 외의 재료는 ‘큐’를 검사하여 이미 큐에 있는지 확인하고 있다면, 해당 요소에 더하며
   그렇지 않다면, 새로 queue에 넣어준다
   
5. queue가 빌 때까지 반복하며, 이후
   answer를 출력한다