https://www.acmicpc.net/problem/2637
시간 1초, 메모리 128MB
input :
- N (3 ≤ N ≤ 100)
- M (3 ≤ M ≤ 100)
- X, Y, K (X를 만드는데 부품 Y가 K개 필요)
output :
- 기본 부품의 수를 한 줄에 하나씩 출력
- 기본 부품의 번호가 작은 것부터 큰 순서가 되도록
조건 :
-
기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다.
-
중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다.
doju님이 추가한 데이터 input
doju님이 추가한 데이터 output
기본적으로, 문제의 설명 형태에서 특정 부품들은 다른 부품들을 통해 만들어진다.
이 문장을 통해 위상정렬을 수행하면 해결하기 편할 수 있다는 것을 알 수 있다.
우선 기본 부품, 완성품을 찾는 것을 수행했다. 이것은 degree의 개수를 통해 알 수 있는데 기본적인 위상정렬을 위한 degree 체킹으로 기본 부품을, reverse_degree를 통해 완성품을 찾을 수 있다. 완성품의 경우에는 반대로 그래프를 그리면 degree가 없으니까 이를 사용했다.
기본 부품들에서 완성품을 향해 그래프 탐색을 수행하는데 이 떄, dfs나 bfs를 사용하게 되면 시간 초과가 발생한다. 재귀 dp를 이용해서 푸신분도 존재하니 탐색을 사용하지 않고 다른 방식으로 하신것 같다.
가장 문제가 된 부분은 기본 부품의 개수를 어떻게 기록하는가 였다.
생각보다 허탈한 방법이 존재했는데 해당 부품에 대해 1 ~ 100 까지 필요한 개수를 다 저장하는거다.
생각보다 적은 범위이기 때문에 공간도 충분하고 생각하기 편리하다.
기본 부품들에 대해서는 자기자신을 1개 필요로 한다고 생각할 수 있어 초기화를 수행한다.
다른 특정 부품들은 += 연산을 통해 필요한 부품들을 누적하도록 한다.
import sys
from collections import deque
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph, value, degree, reverse_degree, nodes = [[] for _ in range(n + 1)], [dict() for _ in range(n + 1)], [0] * (n + 1), [0] * (n + 1), [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
x, y, k = map(int, sys.stdin.readline().split())
graph[y].append(x)
value[y][x] = k
degree[x] += 1
reverse_degree[y] += 1
q, ans = deque([]), []
for i in range(1, n + 1):
if not degree[i]:
nodes[i][i] = 1
q.append(i)
ans.append(i)
root = reverse_degree[1:].index(0) + 1
while q:
node = q.popleft()
if node == root:
break
for next_node in graph[node]:
degree[next_node] -= 1
if not degree[next_node]:
q.append(next_node)
for i in range(1, n + 1):
nodes[next_node][i] += value[node][next_node] * nodes[node][i]
for key in ans:
print(f"{key} {nodes[root][key]}")
