[BOJ]2637. 장난감조립 (python)

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. 먼저, 2차원 인접행렬을 만들고 본인이 부품이 되는 곳을 탐색한다. (ex 5 2 3는 2번 부품 3개가 5번 부품의 재료라는 뜻이고, 나는 이를 2번 인접행렬의 5번 인덱스에 3을 넣겠다. 로 입력받았다)

2. 해당 인덱스의 인접행렬마다 그 인덱스의 부품이 어떤 부품의 재료가 되는지 알 수 있다.

3. 기본 부품들은 초기에 진입차수가 0인 경우이고 (어떤 부품도 재료가 되지 않으므로), 이를 따로 저장하고 queue에도 넣어준다.
4. queue가 끝날 때까지 해당 부품이 재료가 되는, 즉 target 부품에 재료 부품의 모든 것을 넣어준다. ( 5 2 3의 경우, 5번 부품에 2번 부품을 구성하는 기본 부품 * 2를 다 넣어준다)

5. 작업이 끝나면 target 부품의 진입차수를 1 낮춘다.

6. 진입차수가 0이라면 queue에 추가하여 반복한다.

7. 마지막 parts_N번째 부품에는, 이 부품을 만들기 위한 기본부품의 수가 모두 합쳐져 있다.

 

코드

 

 

import sys
import collections



parts_N = int(sys.stdin.readline().strip())

M = int(sys.stdin.readline().strip())
# 부품간의 관계를 나타내기 위한 parts_need, 진입 차수를 표시하는 indegree
parts_need = [[0] * (parts_N + 1) for _ in range(parts_N + 1)]
indegree = [0] * (parts_N + 1)

# 해당 부품이, 어떤 중간 제품의 부품이 되는지 기록한다. ex 5 2 2 라면 2번 부품은 5번에게 2개 필요하므로 2번 부품의 인접행렬에 5번 인덱스에 2를 넣는다.
# parts_need[2][5] = 2, parts_need[part][target] = count
for _ in range(M):
    target, part, count = map(int, sys.stdin.readline().strip().split())
    parts_need[part][target] = count
    indegree[target] += 1


# basic_part에는 기본 부품을 넣는다 ( 초기에 진입차수가 0인 부품들 )
queue = collections.deque()
basic_part = []
for i in range(1, parts_N + 1):
    if indegree[i] == 0:
        queue.append(i)
        basic_part.append(i)
# 기본부품이 인접행렬의 본인 인덱스에 1개를 넣어준다. 이유는 while문에서 등장한다.
for basic in basic_part:
    parts_need[basic][basic] = 1



while queue:
    start = queue.popleft()
# 진입차수가 0인 경우에, 현재 부품이 어떤 부품의 재료인지 나와있다. 이를 읽고, target 부품에 현재 부품의 재료들을 추가해줘야한다.
## 이때 기본 부품들의 경우에는, 기본부품을 구성하는 재료 부품이 전부 0 이므로, 본인 자신은 1로 표시하여 부품을 추가할 수 있게한다.
    for i in range(1, parts_N + 1):
        if parts_need[start][i] > 0 and indegree[i] > 0:
            for basic in basic_part:
                parts_need[i][basic] += parts_need[start][basic] * parts_need[start][i]
            indegree[i] -= 1
            if indegree[i] == 0:
                queue.append(i)

for basic in basic_part:
    print(basic, parts_need[parts_N][basic])