[백준/Python]2367: 장난감 조립

문제

https://www.acmicpc.net/problem/2637
백준 - 문제집 - 0x1A강 - 위상 정렬

 

알고리즘: 다이나믹 프로그래밍, 방향 비순환 그래프, 위상 정렬

---

풀이

 

AI의 도움을 받았던 문제다...🤖

DP + 위상 정렬을 사용해야하는 문제인데, DP에 더 가까워보인다.

 

문제에서 구하고자 하는것은 "필요한 기본부품의 종류와 수"인데,
기본부품 - 완제품 사이 중간부품이 존재한다.
그리고 기본부품은 중간부품, 완제품 모두에 사용될 수 있다.

 

그런고로 이 문제 역시 DFS로 풀려면 살짝 복잡해진다. (계보 복원가 호석 문제를 떠올려보자...)
BFS를 사용하려면 진입차수부터 정리해줘야하는데 무의식적으로 풀다간 실수할수도 있다.

장난감은 (기본부품 - 중간부품 - 완제품) 순으로 만들어져야한다.
즉, 기본부품이 제일 우선이 되어야 하는것이다.

따라서 그래프 정리 시 기본부품에 (중간부품/완제품, 필요한 기본부품의 수)를 저장한다.
진입차수 역시 중간부품/완제품에 1 증가시켜줘야한다.
👉 진입차수가 0인 노드가 기본부품이 되므로 queue에 넣어준다.;

 

그리고 2차원 DP 리스트를 생성해준다.
👉 dp[x][y] = x를 만드는데 필요한 기본부품 y의 갯수

 

본격적인 진행 순서는 다음과 같다.

1. queue에서 현재 노드(curr)를 뽑아냄.
2. curr과 연결된 그래프를 탐색 (연결노드, 갯수)
   • 만약 dp[curr]을 sum 한 값이 0이라면?
     • curr을 만드는데 필요한 기본부품의 갯수가 0이라는 뜻
     • curr = 기본부품인 셈이므로 dp[연결노드][curr]에 갯수를 더해줌
   • 기본부품이 아니라면, curr을 만드는데에 필요한 기본부품의 수를 가져와 계산해줌
     • 모든 장난감을 순회하며 갱신시켜주기
     • dp[연결노드][i] += dp[curr][i] * 갯수
     • (연결노드, 갯수)에서 갯수는 연결노드를 만드는데에 필요한 curr의 갯수!
     • (curr * 갯수)만큼 필요하므로 (curr에 사용된 기본부품의 갯수 * 갯수)를 더해줘야함
   • 진입차수를 1 감소시킴
   • 진입차수가 0이 된다면, queue에 추가함
3. 모든 장난감 번호를 체크하며 결과 출력
   • dp[N][i]: 완제품 N을 만드는데에 필요한 기본부품 i의 갯수
   • 해당 값이 양수일경우, i는 기본부품인 셈
   • (i, dp[N][i])로 (기본부품 번호, 쓰이는 갯수) 출력

 

전체 코드

# DP + BFS 문제
# 메모리: 34968KB / 시간: 56ms
from sys import stdin
from collections import deque


input = stdin.readline

N = int(input())
graph = [[] for _ in range(N+1)]
in_degree = [0] * (N+1)

M = int(input())
for _ in range(M):
    X, Y, K = map(int, input().split())
    # X를 만드려면 Y가 K개 필요함.
    # => 더 기본이 되는 부품이 먼저 만들어져야함.
    graph[Y].append((X, K))
    in_degree[X] += 1

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

# dp[x][y] = x를 만드는데 필요한 기본부품 y의 갯수
dp = [[0] * (N+1) for _ in range(N+1)]

def bfs():
    while queue:
        curr = queue.popleft()

        # nxt = curr을 cnt만큼 필요로 하는 부품
        for nxt, cnt in graph[curr]:
            # 필요한 부품이 0이라면 기본부품이라는 뜻
            if sum(dp[curr]) == 0:
                dp[nxt][curr] += cnt
            else:
                # 기본부품이 아닐경우, curr을 만드는데에 필요한 기본부품 i의 수 * cnt를 더해줌
                for i in range(1, N+1):
                    dp[nxt][i] += dp[curr][i] * cnt

            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)


bfs()
for i in range(1, N+1):
    if dp[N][i] > 0:
        print(i, dp[N][i])

 

풀어도 풀어도 어려운 DP다...

오래된 문제의 풀이를 작성할때는 다시 한 번 풀어보는 편인데, 머리의 존재 이유에 대해 진지하게 고민했다^^

연습만이 답일지다...