백준 2637 [장난감 조립] 파이썬

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

 

# 백준 2637 장난감 조립 - 중복 간선 방식
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())  # 완제품 번호 (1~N)
M = int(input())  # 부품 연결 정보 개수

# 그래프 초기화: graph[a] = a를 만들기 위해 필요한 '작은 부품'들이 연결됨
graph = [[] for _ in range(N+1)]
in_degree = [0 for _ in range(N+1)]  # 진입차수 (선행 부품 개수)
basis = []  # 기본 부품(더 이상 분해되지 않는 부품) 목록
need_toys = [[0 for _ in range(N+1)] for _ in range(N+1)]
# need_toys[x][y] = x를 만들기 위해 필요한 y 부품의 개수

# 입력 처리
for _ in range(M):
    X, Y, K = map(int, input().split())
    # Y 부품 K개로 X를 만든다는 의미
    graph[Y].append((X, K))   # Y → X (K개 필요)
    in_degree[X] += 1

q = deque()

# 진입차수가 0인 노드는 기본 부품
for i in range(1, N+1):
    if in_degree[i] == 0:
        q.append(i)
        basis.append(i)
        need_toys[i][i] = 1  # 자기 자신 1개 필요

# 위상 정렬 시작
while q:
    small_toy = q.popleft()  # 현재 작은 부품
    for big_toy, cnt in graph[small_toy]:
        in_degree[big_toy] -= 1

        # small_toy가 필요하다면, 그에 따른 기본 부품 수를 big_toy에 누적
        for base in basis:
            need_toys[big_toy][base] += need_toys[small_toy][base] * cnt

        if in_degree[big_toy] == 0:
            q.append(big_toy)

# 완제품(N)을 만들 때 필요한 기본 부품 개수 출력
for base in basis:
    print(base, need_toys[N][base])

반복되는 횟수만큼 그래프에 추가하도록 하였다. (큐에도 반복되는 횟수만큼 저장)

 

GPT가 개선된 코드를 제시하여 그것도 첨부한다. (in_degree+=1 하고, 반복수만큼 곱함)

# 백준 2637 장난감 조립 — 카운트 저장 방식
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
M = int(input())

# graph[small] = [(big, cnt), ...] — cnt는 small이 몇 개 필요한지
graph = [[] for _ in range(N+1)]
in_degree = [0] * (N+1)
basis = []
need = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    X, Y, K = map(int, input().split())
    graph[Y].append((X, K))
    in_degree[X] += 1  # 서로 다른 '부품 종류' 만큼만 진입차수 증가

q = deque()
for i in range(1, N+1):
    if in_degree[i] == 0:
        q.append(i)
        basis.append(i)
        need[i][i] = 1

while q:
    small = q.popleft()
    for big, cnt in graph[small]:
        in_degree[big] -= 1
        for b in basis:
            need[big][b] += need[small][b] * cnt
        if in_degree[big] == 0:
            q.append(big)

for b in basis:
    print(b, need[N][b])

K값이 작다면 크게 문제되지 않으나, 큰 경우에는 시간차이가 많이 날 수 있다...!

 

결국, 핵심은 반복되는 node의 cost를 DP로 어떻게 처리할 것이냐이다.