[백준] [파이썬] [위상정렬] 2637번: 장난감 조립

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

2637번: 장난감 조립 문제보기

 

제한시간: 1초
메모리 제한: 128 MB

문제

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

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

---

완제품부터 시작해서 간선의 가중치를 카운트하면 된다고 생각하였으나 메모리초과 문제가 생겼다.

이 문제는 역시 마찬가지로 우선순위가 낮은 것들을 큐에 넣고 시작하는 것이다.

다른 점은 각 노드에서 노드 사이의 간선 가중치를 저장하기 위해 2차원 배열을 사용해야 한다는 것이다.

역시 위상 정렬 문제이니 만큼 그림을 그려주는 것이 좋다.

다음과 같은 프로세스이다.

1. 노드를 연결하고 진입 차수를 저장한다
2. 큐 또는 스텍을 사용하여 진입 차수가 0인 노드들을 전부 넣는다
3. 하나씩 뺀 노드와 연결되어있는 노드의 연결을 해제하고 진입차수를 -1해주며 그때 가중치를 기록한다
4. 진입 차수가 0이면 큐에 넣어준다
5. 반복

1. 노드를 연결하고 진입차수를 저장한다.

 

 

2. 큐 또는 스텍을 사용하여 진입차수가 0인 노드들을 전부 넣는다. 

 

 

3. 하나씩 뺀 노드와 연결되어있는 노드의 연결을 해제하고 진입차수를 -1해주며 그때 가중치를 기록한다

 

4. 진입 차수가 0이면 큐에 넣어준다

 

큐에 노드 2까지 빠지고 -> [3,4]

노드 5의 진입차수가 0이 되어 큐에 넣어준다 -> [3,4,5]

 

5. 큐가 빌때까지 반복하고 needs의 마지막 리스트를 반환한다

 

 

---

정답 코드

import sys
from collections import deque
# sys.stdin=open('input.txt','r')
input = sys.stdin.readline


if __name__=="__main__":
    N=int(input())                  # 1~N-1까지 기본/중간 부품 번호, N은 완제품 번호
    M=int(input())
    graph=[[] for _ in range(1+N)]
    needs=[[0]*(1+N) for _ in range(1+N)]
    arr=[0]*(1+N)
    for i in range(M):
        x,y,k=map(int, input().split()) # x를 만드는데 필요한 y부품이 k개 필요함
        graph[y].append((x,k))
        arr[x]+=1
    
    Q=deque()
    for i in range(1,N+1):
        if arr[i]==0:           # 진입차수가 0인걸 넣어준다.
            Q.append(i)         # 기본 부품 노드들이 넣어진다
    
    while Q:
        x=Q.popleft()                   # 현재 노드
        for node,weight in graph[x]:    # 현재 노드에 연결된 다음 노드와 가중치
            # needs[x]: [0, 0, 0, 0, 0, 0, 0, 0]에서 0의 개수가 N+1이면 기본 부품임
            if needs[x].count(0)==N+1:  # 만약 기본 부품이면 
                needs[node][x]+=weight  # 다음 노드의 현재 노드위치에 현재노드에서 다음노드로 가는데 필요개수
            else:                       # 기본 부품이 아니면
                for i in range(1,N+1):  
                    needs[node][i]+=needs[x][i]*weight  
            
            # 진입차수 -1
            arr[node]-=1
            if arr[node]==0:
                Q.append(node)
    
    for i,x in enumerate(needs[N]):
        if x!=0:
            print(i,x)

 

---