[알고리즘] 크래프톤 정글 2주차 / 알고리즘 中 혼자서 못 푼 문제 정리6(장난감 조립)

BOJ 2637 장난감 조립

난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골2

사용 알고리즘 or 자료 구조 : 위상정렬 / DP

 

처음 생각한 풀이

탑다운 방식으로 최종 제품을 1개 만드는 데 필요한 중간 부품 및 기본 부품들의 개수를 미리 선언해둔 리스트에 더해가며 최종적으로 완성된 리스트에서 indegree가 0인 것들만 출력하는 방식으로 푸는 것이라고 생각했다.

 

그런데 왜인지는 모르겠지만 계속해서 메모리 초과가 떴고, 도대체 왜 그런거지 하고 접근법을 찾아봤다.

사실 접근법을 찾아보니 접근법의 방식들이 메모리 초과가 안 날 만하다고 생각은 들지만, 여전히 원래 방식이 왜 메모리 초과가 나는 지는 이해가 가지 않는다.

구글링 이후 풀이

일단 DP를 사용하는 방법이다. 탑다운, 바텀업 둘 다 있다. 차례차례 설명하도록 하겠다.

1. Top-down dp

우선 위상정렬 알고리즘을 통해 어떤 것이 기본 부품이고 어떤 것이 중간 부품인지 찾고, 어떤 순서로 제작을 해야되는지를 구한다.

 

그 후, 완제품부터 차례 차례 내려오며 각 부품들이 총 몇 개가 필요한지 dp를 이용하여 구하면 된다.

(이게 내 방식이랑 비슷한데 왜 메모리 초과인건지 모르겠다...)

2. Bottom-up dp

우선 위상 정렬을 시작해야하는 것은 동일하다.

 

Top-down과 비슷하게 위상 정렬을 통해 기본 부품을 찾고, 아래에서부터 dp를 이용하여 차근차근 올라가며 완제품까지 완성시키는 방법도 가능하다.

 

하지만 나의 경우는 위상 정렬을 함과 동시에 미리 선언해둔 리스트에 각 기본 부품과 중간 부품을 만드는데 필요한 부품의 종류와 개수를 저장해나가며 그 정보를 이용하는 방식으로 풀었다.

 

즉, 기본 부품을 위상 정렬을 하며 찾은 뒤, 각 중간 부품을 만들 때 필요한 기본 부품의 총 개수를 저장해나가는 것이다.

 

 

 

※ 스 포 주 의 ※

 

 

 

 

코드

import sys

from collections import deque

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

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

indegree = [0 for _ in range(N + 1)]

edge = [[] for _ in range(N + 1)]

for i in range(M):

    a, b, c = map(int, sys.stdin.readline().split())

    edge[b].append((a, c))  # a를 만드는데 b가 c개 필요하다.

    indegree[a] += c

need = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

base = []

queue = deque()

for i in range(1, N + 1):

    if indegree[i] == 0:

        queue.append(i)

        base.append(i)

for node in base:

    need[node][node] = 1

   

while queue:

    cur = queue.popleft()

    for [next, num] in edge[cur]:     ### cur과 연결된 next를 만들기 위해서는 cur이 num개 필요

        for j in range(1, N + 1):

            need[next][j] += need[cur][j] * num

        indegree[next] -= num

        if indegree[next] == 0:

            queue.append(next)

for node in base:

    print(node, need[N][node])