[백준] 2637번 : 장난감조립

2637번: 장난감 조립

2637번: 장난감 조립

📄 문제개요

장난감을 조립하기위하여 장난감의 의존성을 정의되어있는 테이블이 주어진다.

장난감은 N개의 기본부품과 중간부품으로 나누어 지는데 마지막 N번째의 부품의 기본부품의 개수를 구하는 문제이다.

기본부품은 다른 부품으로 조립 할 수 없는 부품이고, 중간부품은 아래와 같이 구성 될 수 있다.

• 중간부품 + 기본부품
• 기본부품 + 기본부품
• 중간부품 + 중간부품

🤔 문제분석

해당문제는 만약 5번부품의 기본부품의 개수를 알게 되었다면 5번 부품을 중간 부품으로 사용하는 부품을 다시한번더 계산 하지 않고 문제를 해결해야한다. 탑다운 방식을 활용하여 문제를 해결하였다.

calculated 1차원 테이블과 dp 2차원 테이블을 구성하였다.

• calculated테이블은 현재 장난감의 기본부품 개수가 구해졌는지에 대한 확인용 테이블이다.
• dp 2차원테이블은 해당 기본 부품들의 정보를 가지고있다. ( 기본부품은 자기자신을 1로 가지고 있다)

📝 의사코드

1. 탑다운 방식으로 재귀 함수를 정의한다.
2. 종료조건 : 이미 계산된경우, 기본 부품인경우
3. 기본 부품인경우는 자기자신을 1로 초기화 한뒤, 계산되었다고 체크한다.
4. 이미 계산된경우는 dp테이블을 리턴한다.
5. 계산 알고리즘 : 구성 부품을 순회하면서, 구성부품의 dp테이블을 참조하여 결과를 누적한다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

toy = [[] for _ in range(N+1)]
for _ in range(M):
    X, Y, K = map(int, input().split())
    toy[X].append((Y, K)) # 기본부품 Y가 K개 필요하다.
    

calculated = [False for _ in range(N+1)]
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
def dfs(item):
    #print("item", item)
    if not toy[item]: # 기본부품인경우
        dp[item][item] = 1
        calculated[item] = True
        return dp[item]
    
    if calculated[item]:
        return dp[item]
    
    for new_item in toy[item]:
        temp = dfs(new_item[0])
        for i in range(N):
            dp[item][i] += temp[i] * new_item[1]
    
    calculated[item] = True
    return dp[item]

ans = dfs(N)
for i, r in enumerate(ans):
    if r:
        print(i, r)

🎯 피드백 및 개선사항

재귀방식으로 문제를 해결하면 문제를 쉽게 해결할 수 있습니다. 그러나 시간복잡도와 메모리 복잡도 측면에서 반복문을 따라 잡을 수 없습니다. 최적화가 필요한경우는 반복문으로 시간복잡도를 최적화 할 수 있습니다.

❓다른사람은 어떻게 풀었을까?

대부분 DFS로 문제를 해결하였으나, BFS로 문제를 해결하신분이 있어 코드를 참조 하였습니다.

재귀방식 장점 : 읽기 쉬운 코드로 작성가능하다.

반복방식 장점 : 코드가 읽기가 어려우나, 시간복잡도와 공간복잡도 최적화를 할 수 있다.

import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
needs = [[] for _ in range(N+1)]
indg = [0]*(N+1)
post = [[] for _ in range(N+1)]
dp = [dict() for _ in range(N+1)]
for i in range(M):
    X, Y, Z = map(int, sys.stdin.readline().split())
    needs[X].append([Y,Z]) #X는 Y를 Z개
    indg[X] += 1
    post[Y].append(X)

q = []
for i in range(1,N+1):
    if not indg[i]: q.append(i)

order = []
check = [False]*(N+1)
while q:
    node = q.pop()
    check[node] = True
    order.append(node)
    for i in range(len(post[node])):
        y = post[node][i]
        indg[y] -= 1
        if not check[y] and not indg[y]:q.append(y)

for i in range(len(order)):
    cur = order[i]
    prevs = needs[order[i]]
    for j in range(len(prevs)):
        prev, cnt = prevs[j]
        for key in dp[prev].keys():
            value = dp[prev][key]
            if key not in dp[cur]: dp[cur][key] = 0
            dp[cur][key] += cnt*value

        if not len(dp[prev]):
            if prev not in dp[cur]:dp[cur][prev] = 0
            dp[cur][prev] += cnt

for key in sorted(dp[N].keys()):
    print(key, dp[N][key])