[BOJ] 2637 장난감 조립(Python3)

문제

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

예를 들어보자. 기본 부품으로서 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 이하이다.

정답 코드

from collections import deque
n = int(input())
m = int(input())

dic = defaultdict()

basic = [i for i in range(1, n + 1)]
graph = [[0, []] for _ in range(n + 1)]

for i in range(m):
    a, b, c = case[i]
    graph[a][0] += 1
    graph[b][1].append([a, c])
    
for g in graph:
    g[1].sort()
needs = [[0] * (n + 1) for _ in range(n + 1)]
q = deque()

for i in range(1, n + 1):
    if graph[i][0] == 0:
        q.append(i)

while q:
    now = q.popleft()
    
    for g in graph[now][1]:
        next_node, value = g
        
        if needs[now].count(0) == n + 1:
            needs[next_node][now] += value
        else:
            for i, need in enumerate(needs[now]):
                if need != 0:
                    needs[next_node][i] += value * needs[now][i]
        graph[next_node][0] -= 1
        
        if graph[next_node][0] == 0:
            q.append(next_node)
            
for i, need in enumerate(needs[n]):
    if need != 0:
        print(i, need)
        
    
    
    
    

1 16
2 16
3 9
4 17

문제 풀이

이 문제는 처음에 DFS 문제라고 생각해서 DFS를 사용했는데 메모리 초과가 났다.

그래서 찾아보니 위상정렬로 푸는 문제였다.

알고리즘은 다 안다고 생각하면 왜 또 새로운게 나오는건지… 백준을 풀다보면 별의별 알고리즘을 접하게 된다.

이 문제가 위상정렬 문제인 이유는 사이클이 생기지 않고 시작지점, 종료지점이 명확하기 때문이다. 위상정렬 알고리즘은 이처럼 사이클이 생기지 않는 경우에 하나를 완료하기 위해서는 이전 작업을 진행해야 하는 경우 사용가능하다.

(동빈나 유튜브 - 위상 정렬 알고리즘)[https://www.youtube.com/watch?v=qzfeVeajuyc&t=453s]

위의 링크에서 위상 정렬 알고리즘에 대해 배울 수 있다.

위상 정렬 알고리즘은 진입차수가 0인 노드들 부터 하나씩 처리해가며 해당 노드와 이어진 노드들에 가중치를 추가해준 뒤, 해당 노드의 연결을 끊는 것을 반복하며 마지막 노드가 남을때까지 이를 반복한다.

위 문제의 경우, 기본 부품들이 모여 중간 부품이 되고, 중간부품이 모여 최종 부품이 되므로 앞서 서술한 방식을 사용 가능하다.

기본 부품 = 진입차수가 0인 노드

이를 통해 기본 부품을 다음 노드로 가중치를 더하고 해당 연결을 해제하면, 중간 부품이 다시 기본부품이 된다. 이를 반복하며 최종 부품 하나의 노드가 남을때까지 이를 반복하며 이 가중치를 표를 통해 기록하면 된다.

사실 설명을 봐도 어차피 위상정렬에 대한 이해가 없다면 이해하기 어려우니 상기 첨부한 링크에서 위상정렬을 꼭 학습하고 문제를 푸는 것을 권장한다.