장난감 조립 - 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 이하이다.
풀이
위상 정렬로 위 문제를 풀이할 수 있다.
위상정렬
위상정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다.
진입차수 : 특정노드로 들어오는 간선의 개수
진출차수 : 특정한 노드에서 나가는 간선의 개수
위상정렬법은 다음과 같은 절차를 거친다.
- 진입차수가 0인 모든 노드를 큐에 넣는다.
- 큐가 빌 때까지 다음의 과정을 반복한다.
2-1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선 그래프를 제거한다.
2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. - 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과가 된다.
위 절차는 큐를 이용하여 구현할 수 있으며, 이는 bfs 메소드의 범주 안에 속한다고 할 수 있다.
다음의 코드는 정답이다.
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)] # 간선 정보.
infoarr = [[0]*(N+1) for _ in range(N+1)] # 특정부품을 만드는 데에 필요한 부품 번호, 갯수 정보.
inDegree = [0 for _ in range(N+1)] # 진입차수 배열. (진입차수가 0이 되었다면, 큐에 해당 정점을 삽입)
q = deque()
for _ in range(M):
X, Y, K = map(int, input().rstrip().split())
graph[Y].append([X, K])
inDegree[X] += 1
for n in range(1, N+1):
if inDegree[n]==0:
q.append(n)
infoarr[n][n] = 1
while q:
curr_node = q.popleft()
for next_node, cnt in graph[curr_node]:
for i in range(1, N+1):
infoarr[next_node][i] += cnt*infoarr[curr_node][i]
inDegree[next_node] -= 1
if inDegree[next_node]==0:
q.append(next_node)
for j in range(1, N+1):
if infoarr[N][j]:
print(f'{j} {infoarr[N][j]}')다음은 문제에서 제공하는 예제 입력 1이다. 
문제 풀이를 하며 느낀 바로는 각 노드 간의 정보가 어디에서 어디로 향하는지, 즉 간선의 방향성을 이해하는 것이 핵심인 것 같다.
아래의 코드를 보자.
for _ in range(M):
X, Y, K = map(int, input().rstrip().split())
graph[Y].append([X, K])
inDegree[X] += 1 "X를 만드는 데에 Y가 K만큼 필요하다."는 정보를 graph[Y].append([X, K])로 구현할 수 있다. 다음과 같은 형태가 될 것이다. 예제 입력 1을 기준으로 위 코드를 거치면, 간선 정보를 담는 변수 graph가 구성되며 이는 다음과 같다. 
"X를 만드는 데에 Y가 K만큼 필요하다."는 말인즉 그래포 도표로 나타냈을 때 Y로부터 뻗어나오는 X에 대한 간선이 1개 생기며, 그 가중치가 K라는 게 된다. 간선의 숫자를 나타내는 변수, 즉 즉 진입차수 변수인 inDegree의 인덱스 X째 원소의 값을 1만큼 증가시켜 그 간선의 수를 책정해준다. 위 코드를 거치면, 변수 inDegree가 구성되며 이는 다음과 같다. 
이 다음으로부터 부품에 대한 관계를 정리하기 시작할 것이다. 변수 infoarr는 이차원배열로, 원소의 행 인덱스가 부품번호, 그 원소의 열 인덱스와 값(value)이 각 그 해당 부품을 만들 하위 부품 번호와 갯수이다. 아래의 코드를 보자.
for n in range(1, N+1):
if inDegree[n]==0:
q.append(n)
infoarr[n][n] = 1이 코드를 거치면 진입차수가 0인, 즉 다른 하위 부품에 의해 만들어지지 않는 '기본 부품'만 infoarr에 담길 것이다. 담는 방식은 infoarr[n][n] = 1, 즉 "n번 부품을 만드는 데에 n번 부품이 1개 필요하다"는 식이다.
다시 말해 위 코드는 infoarr에 대한 초기 설정같은 수행이다. 위 코드를 거치면 infoarr는 다음의 상태가 된다. 
동시에 큐 변수 q 역시 기초 부품인 부품만 걸러져 담기게 될 것이다. 아래와 같은 상태가 된다.
우린 이제 graph와 q를 이용해 본격적인 부품에 대한 관계를 정리하기 시작할 것이다.
이제 다음의 코드를 보자.
아까 변수 infoarr는 원소의 행 인덱스가 부품번호, 그 원소의 열 인덱스와 값(value)이 각 그 해당 부품을 만들 하위 부품 번호와 갯수라고 했다.
curr_node는 현재 while문에서 우리가 정보를 확인해 볼 부품이자, next_node를 만드는 데에 사용되는 부품 중 하나이다. 우리는 이 while문 수행 한 번마다 next_node에 대한 정보(필요 부품과 각 필요 갯수)를 기록하는 것이다. for문 수행 한 번 마다 필요 부품 1번 몇 개 필요, 필요 부품 2번 몇 개 필요... 과 같이 기록해나간다.
while q:
curr_node = q.popleft()
for next_node, cnt in graph[curr_node]:
for i in range(1, N+1):
infoarr[next_node][i] += cnt*infoarr[curr_node][i]
inDegree[next_node] -= 1
if inDegree[next_node]==0:
q.append(next_node)한 줄 정리해서 넣을 때마다 진입차수-1 씩을 빼주고, 그렇게 next_node에 대한 간선 및 가중치 정보에 대해 다 기록했다면 q에 next_node를 넣어준다. 고로 next_node는 이 다음 차례의 while문 회차 때 확인해 볼 부품이 된다.
위 수행을 더 이상 수행할 거리가 없을 때까지 즉 q==[]일 때까지 반복한 뒤, 완성된 infoarr는 다음과 같다.
(참고로 q와 inDegree는 당연히 전부 앵꼬 난 상황일 것이다. 아래와 같이.)
이제 완성된 infoarr에서, 우리는 가장 상위의 부품에 대한 정보를 담은 행 infoarr[-1](==infoarr[N])을 추출하면 되는 것이다. 차례대로 문제에서 요구한 대로 프린트 해준다.
for j in range(1, N+1):
if infoarr[N][j]:
print(f'{j} {infoarr[N][j]}')