[위상정렬] 백준 장난감 찾기 2637번 with Python3 ★★

 

https://www.acmicpc.net/problem/2637

2637번: 장난감 조립

문제

 

정답 풀이

import sys
from collections import deque
input = sys.stdin.readline

# N = 완제품 번호, 1,2,3,...N-1 까지 기본부품 혹은 중간부품
N = int(input().rstrip())
# M = 어떤 부품을 완성하는데 필요한 부품들의 관계 개수
M = int(input().rstrip())


arr = [[] for _ in range(N+1)]
ind = [0] * 101  # 진입차수
v = [[0] * (N+1) for _ in range(N+1)]  # 갯수를 저장할 배열
# 2차원 배열: v[i] = 부품 번호 i / v[i][j] = j로 i를 만드는데 필요한 개수

for i in range(M):
    # cur 만들어야할 부품 prev 사용되는 부품 val 갯수
    cur, prev, val = map(int, input().rstrip().split())
    arr[prev].append((cur, val))  # prev 기준으로 cur와 cur 제작에 필요한 부품갯수 저장
    ind[cur] += 1  # 진입차수 올려주기

q = deque()

for i in range(1, N+1):
    if ind[i] == 0:  # 진입차수가 0인 기본 부품에서 시작
        q.append(i)
        v[i][i] = 1  # 기본 부품만 시작값을 1로 할당함

#위상정렬
while q:
    here = q.popleft()

    for next in arr[here]:

        #arr[here]  = next  = (cur, val)
        # here 지금 부품 번호
        # next[0] 다음 부품 번호 / here로 만들 수 있는 부품 번호
        # next[1] 다음 부품에 필요한 지금 부품 개수

        for i in range(1, N+1):
        
            # v[i][j] = j로 i를 만드는데 필요한 개수
            # 이전 부품제작에 필요한 모든 부품 개수 v[here][i]에 다음 부품 제작에 필요한 수 next[1]을 곱한다.

            v[next[0]][i] += next[1] * v[here][i]

# ex) v[2] = [0,2,1,0] (2를 만드는데 1이 두개 필요하다. 1은 기본부품이기에 시작값으로 설정되어있는것)
# ex) here = 2 / next = (3, 3) (2로 3을 만드는데 3개가 필요)
# ex) for문을 돌면서 모든 v[here][i]에 next[1] =3 을 곱한 값을 각 v[next[0]][i] 에 추가
# ex) v[next[0]] = [0, 6, 3, 0] ( 3을 만드는데 1이 6개, 2가 3개 필요, 3은 기본 부품이 아님.)


        # 진입차수 감소
        ind[next[0]] -= 1

        # 진입차수가 0이 될 경우 q에 넣기
        if ind[next[0]] == 0:
            q.append(next[0])


for i in range(1, N+1):
    if v[N][i]:  # 기본 부품 외에 다른건 시작이 0이었기 때문에 세지 않음
        print(f"{i} {v[N][i]}")

출처:https://kspsd.tistory.com/17

해설

코드마스터님의 해답을 보고 문제를 이해해봤다. 

 

문제를 딱 봤을때 전혀 풀이과정을 구상할 수가 없었는데 막상 답을 보고 나니, 상당히 위상정렬의 기본적인 구조 그대로 진행되는 문제였다. 아직 위상정렬에 익숙하지 않는듯. 

 

다만 각 부품별로 지금의 부품을 만드는데 필요한 개수들을 모두 저장하는 v라는 2차원 배열을 만들어 계속해서 더해주며 올라가는 식의 풀이 발상은 아직도 그냥 생각해낼 자신이 없다.