BOJ 2637 장난감 조립

LONGNEW·2021년 12월 29일
0

BOJ

목록 보기
280/333

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]}")

0개의 댓글