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

문제

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

---

문제 설명

1.   여러 가지 부품을 조립하여 장난감을 만든다.
   1. 기본 부품은 재료가 필요 없다.
   2. 중간 부품은 기본 부품들을 이용해서 만든다.
   3. 완제품은 중간 부품 혹은 기본 부품을 사용해 만든다.
2. N이 주어지면 1부터 N-1번째까지는 기본 부품 혹은 중간 부품, N은 완제품의 번호를 나타낸다.
3. 완제품을 만들려면 기본 부품이 총 몇 개 필요한지 출력한다.

---

풀이

문제를 처음 봤을 때 가장 높은 노드 즉, 완제품부터 순차적으로 너비 탐색을 진행하면 최종적으로 기본 부품들의 개수를 구할 수 있을 것이라 생각했다. 하지만 BFS로는 풀리지 않았다. 왜냐하면 높은 번호의 중간 부품이 하위 부품을 갱신한 상태에서, 나중에 그 하위 부품을 재 갱신할 때 값이 일치하지 않는 문제가 생기기 때문이다.

 

값이 중복 갱신되는 문제를 해결하기 위해 기본 부품들을 필요로 하는 부품들에게 차례대로 넣어주는 방식을 떠올렸다.

 

기본부품들을 중간 부품들에게 넣어주게되면, 중간 부품들은 기본 부품들로 구성될 것이고 최종적으로 그 중간 부품들을 완제품에 넣어주게 되면 완제품 또한 기본 부품들로 구성될 것이다.

 

위 같은 발상을 그래프로 나타내면 진입차수가 존재하는 그래프를 만들 수 있다. 따라서 위상정렬 알고리즘을 통해 문제를 해결했다.

 

1. 차수가 0인 노드(기본 부품)를 탐색한 후 방문처리한다.
2. 해당 노드(부품)을 필요로 하는 노드들에게 필요한 개수만큼 더해준다.
3. 차수를 감소시킨다.
4. 완제품의 부품 리스트를 출력한다.

---

코드

import sys
input = sys.stdin.readline

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

degree = [0 for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
for _ in range(int(input())):
    x,y,k = map(int,input().split())
    graph[y].append([x,k])
    degree[x] += 1

res = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(1,N+1):
    if not degree[i]:
        res[i][i] = 1

visited = [0 for _ in range(N+1)]
for _ in range(N):
    v1 = 0
    for i in range(1,N+1):
        if degree[i] == 0 and not visited[i]:
            v1 = i
            visited[i] = 1
            break
    for v2,cost in graph[v1]:
        for i in range(1,N+1):
            res[v2][i] += res[v1][i]*cost
        degree[v2]-=1

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

---

시간복잡도

• 위상정렬의 시간 복잡도는 정점 + 간선, O(V+E)이다.
• 위상정렬을 한 후 부품들을 더해주기 위해 N번 반복하므로 약 $O((V+E)*N)) = O(200*100) = O(10^4)$의 시간복잡도를 가진다.