2637 - 장난감조립
[Gold II] 장난감 조립 - 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 이하이다.
입력예시
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
위의 입력을 다음과 같이 DAG그래프로 나타낼 수 있다.
풀이
-
처음에 기본부품과 중간부품의 관계를 인접리스트 형태(amounts)로 나타낸다.
기본부품인 1이 중간부품인 5에 2개가 필요하다는 의미이다.
-
마지막 장난감을 만들기 위해서는 중간부품들도 여러개가 필요하기 때문에 인접행렬 형태로 누적합들을 더해주기 위해 일단 tables라는 2차원 배열을 만들어 0으로 초기화를 해둔다.
-
진입차수를 파악하기 위해 indegree 리스트를 만들어 인접리스트를 만들 때 1씩 더해주어 업데이트한다.
-
이렇게 만든 진입차수가 0인 부분이 기본부품을 의미한다.
-
큐에도 기본부품부터 시작하기 위해 진입차수가 0인 부품부터 담아준다.
- 기본부품이 뭔지 파악하기 위해 starts라는 리스트를 만들어 Indegree가 0인 부분을 담아둔다.
-
큐가 빌 때까지 하나씩 빼서 반복문을 통해 현재 인접리스트를 확인하여 어디에 해당부품이 몇개가 필요한지 파악한다.
- 만약 현재 부품이 기본부품이라면 인접리스트에서 파악한 부품에 대입한다.
- 만약 현재 부품이 중간부품이라면 현재 자기가 가지고 있는 부품의 수를 필요한만큼 곱해서 그 부품으로 이루어진 부품의 값에 곱해서 더한다.
- Indegree 리스트에서 확인한 간선을 하나 삭제한다.
- 만약 간선을 삭제했는데 indegree가 0이 된다면 큐에 삽입한다.
-
큐가 비면 모든 간선들을 확인했다는 뜻으로 마지막 줄의 기본부품의 필요수를 출력한다.
코드
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
m = int(input())
amounts = [[] for _ in range(n + 1)]
tables = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
indegree = [0 for _ in range(n + 1)]
starts = []
for _ in range(m):
start, end, cost = map(int, input().strip().split())
amounts[end].append((start, cost))
indegree[start] += 1
def solution():
q = deque()
for i in range(1, n + 1):
if indegree[i] == 0:
q.append(i)
starts.append(i)
while q:
now = q.popleft()
for amount in amounts[now]:
e, c = amount
# 기본부품 더하기
if now in starts:
tables[e][now] = c
# 중간부품 더하기
else:
for i in range(1, n + 1):
tables[e][i] += tables[now][i] * c
indegree[e] -= 1
if indegree[e] == 0:
q.append(e)
solution()
for i in starts:
print(i, tables[n][i])