[BOJ/Python] 2637_장난감 조립

문제 출처:https://www.acmicpc.net/problem/2637

2637번: 장난감 조립

문제

우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다.

예를 들어보자. 기본 부품으로서 1, 2, 3, 4가 있다. 중간 부품 5는 2개의 기본 부품 1과 2개의 기본 부품 2로 만들어진다. 그리고 중간 부품 6은 2개의 중간 부품 5, 3개의 기본 부품 3과 4개의 기본 부품 4로 만들어진다. 마지막으로 장난감 완제품 7은 2개의 중간 부품 5, 3개의 중간 부품 6과 5개의 기본 부품 4로 만들어진다. 이런 경우에 장난감 완제품 7을 만드는데 필요한 기본 부품의 개수는 1번 16개, 2번 16개, 3번 9개, 4번 17개이다.

이와 같이 어떤 장난감 완제품과 그에 필요한 부품들 사이의 관계가 주어져 있을 때 하나의 장난감 완제품을 조립하기 위하여 필요한 기본 부품의 종류별 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주어지고, 그 다음 M개의 줄에는 어떤 부품을 완성하는데 필요한 부품들 간의 관계가 3개의 자연수 X, Y, K로 주어진다. 이 뜻은 "중간 부품이나 완제품 X를 만드는데 중간 부품 혹은 기본 부품 Y가 K개 필요하다"는 뜻이다. 두 중간 부품이 서로를 필요로 하는 경우가 없다.

출력

하나의 완제품을 조립하는데 필요한 기본 부품의 수를 한 줄에 하나씩 출력하되(중간 부품은 출력하지 않음), 반드시 기본 부품의 번호가 작은 것부터 큰 순서가 되도록 한다. 각 줄에는 기본 부품의 번호와 소요 개수를 출력한다.

정답은 2,147,483,647 이하이다.

예제 입력 1

7
8
5 1 2
5 2 2
7 5 2
6 5 2
6 3 3
6 4 4
7 6 3
7 4 5

예제 출력 1

1 16
2 16
3 9
4 17

---

풀이

 

기본 부품의 경우, 그냥 존재하지만 중간 부품의 경우 기본 부품을 이용하여야 만들 수 있다. 최종 완제품의 경우 또한 중간 부품과 기본 부품을 이용하여야 만들 수 있다.

 

문제에서 주어진 조건을 이용하여 단순하게 해결하려고 하였으나 메모리 초과가 나왔다.

메모리 초과가 나온 코드이다.

import sys
import collections
 
def solve(n):
    queue = collections.deque()
    queue.append((n,1))
 
    while queue:
        part,count = queue.popleft()
        if part<min_part:
            result[part]+=count
        
        for next in graph[part]:
            queue.append((next[0],next[1]*count))
 
 
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
 
graph = [[] for _ in range(n+1)]
 
min_part = n
for _ in range(m):
    x,y,k = map(int,sys.stdin.readline().split())
    graph[x].append((y,k))
    if x<min_part:
        min_part=x
 
result = [0 for _ in range(min_part)]
 
solve(n)
 
for i in range(1,min_part):
    print(i,result[i])

우선 이 코드에는 메모리 초과 외에도 한 가지 틀린 부분이 있다. 

그 부분에 대해서는 조금 이따 다루기로 하고, 우선 메모리 초과가 나온 이유에 대하여 생각해보자.

 

이 코드의 solve 함수의 경우 다음의 순서로 동작한다.

1. 완제품을 큐에 넣는다. 완제품 1개를 만드는데 필요한 부품의 개수를 구해야 하므로 (n,1)을 큐에 넣었다.
2. 큐에 원소가 존재하는 동안 반복한다.
3. part와 count를 꺼낸다. count는 현재 필요한 part의 개수이다.
4. 만약 part가 기본 부품이라면 result [part]에 count를 더해준다.
5. 기본 부품이 아니라면 중간제품 혹은 완제품이므로, 이를 구성하는 다른 부품들을 graph에서 찾아낸다.
6. 큐에 ((필요한 하위 부품), (필요한 하위 부품의 개수 * ( 필요한 현재 부품의 개수))를 넣는다.
7. 최종적으로 이 과정을 마치고 나면 기본 부품의 개수를 구할 수 있다.

하지만 이 방식의 문제점은 이미 수행한 과정을 반복한다는 것이다.

예를 들어 문제에서 7번을 만들기 위해서는 5번이 필요하다. 그런데 6번을 만들기 위해서도 5번이 필요하다. 위 코드에서는 7번을 만들기 위한 (5,~)가 큐에 들어가고, 6번을 만들기 위한 (5,~) 또한 큐에 들어간다.

그런데 5를 만들기 위해서는 1과 2가 필요하다. 그렇게 되면 1과 2 또한 (5,~)에 대하여 각각 두 번씩 수행됨을 알 수 있다. n의 크기가 커지면 커질수록 중복되는 경우가 더 늘어나므로 메모리 초과가 나올 수밖에 없다고 결론을 내렸다.

 

해결하기 위하여 동적계획법과 위상정렬을 이용하였다.

그전에 이 코드에서 틀린 부분을 짚고 가자면, 문제를 잘못 이해했다고 할 수 있다.

기본 부품이 낮은 수, 중간 부품과 완제품이 큰 수라고 생각을 해서 코드를 작성하였고, 그래서 (기본 부품)과 (중간 부품, 완제품)의 경계를 구하기 위하여 min_part라는 변수를 사용하였다.

 

[기본부품, 기본부품,...., 기본부품, 중간부품, 중간부품, 중간부품,... , 중간부품, 완제품]

이렇게 구성되어 있는 줄 알았다.

 

하지만, 부품의 번호는 기본 부품과 중간 부품과는 연관이 없어 이 부분 또한 수정하여 코드를 작성하였다.

코드는 다음과 같다.

 

import sys
import collections
 
def topological_sort(n):
    queue = collections.deque()
    for i in range(1,n+1):
        if indegree[i]==0:
            dp[i][i]=1
            queue.append(i)
 
    while queue:
        part = queue.popleft()
 
        for next in graph[part]:
            for i in range(1,n+1):
                dp[next[0]][i] += dp[part][i] * next[1]
                
            indegree[next[0]]-=1
            if indegree[next[0]]==0:
                queue.append(next[0])
 
 
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
 
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
graph = [[] for _ in range(n+1)]
indegree = [0 for _ in range(n+1)]
 
for _ in range(m):
    x,y,k = map(int,sys.stdin.readline().split())
    graph[y].append((x,k))
    indegree[x]+=1
 
topological_sort(n)
 
for i in range(1,n+1):
    if dp[n][i]!=0:
        print(i,dp[n][i])

 

• 우선 처음부터 indegree가 0인 부품들은 기본 부품이라고 할 수 있다.
• dp [i]의 경우, i번 부품을 만들기 위한 부품들의 개수라고 할 수 있다.
• 예를 들어 dp [i][j]라면 i번 부품을 만들기 위하여 필요한 j번 부품의 개수이다.
• 기본 부품의 경우, 다른 부품이 필요 없고 오직 자기 자신만 존재하므로 dp [i][i]를 1로 초기화하고 큐에 넣어줬다.
• 큐에서 부품을 하나 꺼내고, 이 부품을 이용하여 만들 수 있는 중간 부품과 완제품이 있는지 확인한다.
• 만약 존재한다면 dp [중간부품]에 dp [현재부품] * 필요한 개수를 더해준다.
• 그 후 indegree를 1 감소시키고, 만약 0이 되었다면 해당 중간부품은 더 이상 다른 부품이 필요 없다는 뜻이고, dp [중간부품]이 중간 부품을 만들기 위하여 필요한 기본 부품들의 개수가 된다.
• 그러므로 큐에 해당 중간부품을 넣어준다.
• 이 과정을 마치게 되면 dp [n]은 n번 부품(완제품)을 만들기 위한 기본 부품들의 개수가 저장되게 된다.
• 이를 출력한다.