토이스토리 (백준 2637 : 장난감 조립)

2637번: 장난감조립 (acmicpc.net)

2637번: 장난감조립

 

이 문제를 보면서 프라모델이 생각났다.

작은 부품들로 중간 부품을 만들고, 중간 부품들로 큰 부품을 만들고, 큰 부품을 조립하여 완성시킨다.

 

정말 기본 부품의 경우, 중간 부품 하나를 만들기 위해 작은 부품을 모두 떼놨다가 잃어버려서 제대로 못만드는 경우도 있어서 곤혹스러웠던 기억이 있다.

 

그러니 프라모델만들 때에는 딱 필요한 부품만 뗀 뒤에 작업을 진행하도록 하자.

 

그러고보니 프라모델 안만든지도 꽤 오래되었다.

 

일단 위상정렬 문제이기 때문에 indegree와 outdegree를 이용한 위상정렬 풀이법으로 접근해보겠다.

이론적인 부분은 다른 사이트를 참조해주길 바란다.

 

 

문제는 다음과 같다. 

 

완제품 번호는 7번이다.

 

완제품을 만들기 위해서는 No.6부품이 3개, No.5부품이 2개, No.4부품이 5개가 필요하다.

 

No.6부품을 만들기 위해서는 No.5부품 2개, No.3부품 3개, No.4부품 4개가 필요하고

No.5부품을 만들기 위해서는 No.1부품 2개, No.2부품 2개가 필요하다.

 

No.1~4 부품은 기본부품이다. 

 

이를 도식화하면 다음과 같다.

뭔놈의 장난감이 이렇게 복잡해

그리고 우리는 완제품 하나를 만들기 위해서, 얼마만큼의 많은 기본부품이 필요한지 알아야한다.

 

물론, 데이터를 줄 때, '기본부품이 몇 번이다' 라는 정보는 주지 않기 때문에 기본부품이 어떤 번호인지 우리도 파악해야한다.

 

그렇다면 정답으로 기본 부품의 갯수를 출력해야하므로 어떤 로직에서 마지막에 도달하는 것은 기본 부품이 되어야한다.

이것을 반대로 말하면 최종부품부터 시작해야된다는 것이다.

 

그래서 최종부품이 중간부품을 만들려면 몇번이 몇개가 필요한지를 중간부품 단계로 넘기고,

중간부품에서는 기본부품이 몇개가 필요한지를 또 넘겨야한다.

 

이를 위해서 화살표를 반대로 바꿔보겠다.

 

이렇게 보면 감들이 오시는가?

 

7번 부품을 만들기 위해서는 5번 2개, 6번 3개, 4번 5개가 필요하다.

입력 데이터를 보자.

이제 이 입력 데이터를 어떤식으로 해석해야되는지 감이 온다.

입력데이터 중에 [7 5 2] [7 6 3] [7 4 5]가 보인다. 이 정보를 저장해야한다.

 

입력 데이터를 [x, y, EA]라 하자. x를 만들기 위해서 y가 EA개 필요하다는 것이다.

 

그러면 need_parts라는 리스트를 만들고 이는 2차원 배열이다. 길이는 N+1이고 (idx:7에 7번 부품에 관한 정보를 집어넣기 위해서, 0번은 그냥 빈자리로 둔다.), 이 안에 [x, EA]가 들어간다.

 

즉, 7번 부품(완제품)을 만들기 위해서 무엇이 얼마만큼 필요한지를 볼려면 need_parts[7] 을 보면 되고

need_parts[7] = [[5,2], [6,3], [4,5]] (5번이 2개, 6번이 3개, 4번이 5개 필요하다.) 라는 뜻이 된다.

 

이를 코드로 구현하면 다음과 같고,

need_parts = [[] for row in range(N+1)]
for m in range(M):
    x, y, EA = map(int,sys.stdin.readline().split())
    need_parts[x].append([y,EA])

 

위 입력데이터를 넣으면 need_parts는 다음과 같다.

예제 데이터의 need_parts

5번은 [[1,2], [2,2]]

6번은 [[5,2], [3,3], [4,4]]

7번은 [[5,2], [6,3], [4,5]] 가 되는 것을 알 수있다.

 

여기서 눈에 띄는 것은, 1번부터 4번은 공란이라는 것이다.

 

즉! 1번부터 4번이 기본 부품이라는 것을 이를 통해서 알 수있다.

 

그럼 이제 다음 단계로 가보자.

아까 말했듯이, 최종부품부터 진행해야한다.

 

최종부품이 무엇인지 어떻게 아는가?

 

이 그림를 다시보자.

 

화살표를 받기만 하는 부품은 기본부품이다. 

반대로 말하면, 화살표를 받지 않는 부품( 필요로 되지 않는 부품 )은 최종 부품이 된다.

 

하지만, need_parts에서 기본 부품은 빈 리스트이라는 것을 알았지만, 중간부품이나 최종부품을 구별할 수는 없다.

이 때문에 우리는 별도의 리스트를 만들어서 최종부품인지, 중간부품인지 파악해야한다.

 

여기서 need_parts를 만들었던 코드를 다시보자

need_parts = [[] for row in range(N+1)]
for m in range(M):
    x, y, EA = map(int,sys.stdin.readline().split())
    need_parts[x].append([y,EA])

여기서 필요로 되는 부품은 y이다.

 

그렇다면 need_parts를 만들어 줄 때마다, y를 인덱스로한 리스트도 만들어서 카운트해보자

need_parts = [[] for row in range(N+1)]
parts_needed = [0]*(N+1)

for m in range(M):
    x, y, EA = map(int,sys.stdin.readline().split())
    need_parts[x].append([y,EA])
    parts_needed[y] += 1

 

이러면 입력데이터를 다 받았을 경우 다음과 같다.

 

0번 자리는 신경쓰지 말자. 빈자리다.

parts_needed는 해당 부품이 화살표를 몇개나 받고있는지 알려주고 있는 것이다.

 

7번자리가 0인 것이 보이는가? 확실히 그래프에서도 7번 부품은 최종부품(완제품)이기 때문에 받고있는 화살표가 0이었다.

즉, 최초 parts_needed에서 값이 0인 곳, 7번 부품이 최종 부품이 된다.

 

이 두개를 조합해보자.

 

 

예제 데이터의 parts_needed

에제 데이터의 need_parts

 

for i in range(1,N+1):

        if parts_needed[i] == 0:

            for j in need_parts[i]:
                EA_list[j[0]] += j[1]*EA_list[i]
                parts_needed[j[0]] -= 1

 

for i in range(1,N+1): 로 parts_needed에서 0인 자리를 찾는다. (idx는 1부터 N까지다.)

그 자리를 idx(i)로 받아와서 다시 한 번 for문을 돌려준다.

 

for j in need_parts[i]: 로 need_parts[i]에 있는 요소들을 불러온다. 

예를 들어 첫번째 j는 [5, 2]가 될 것이다.

 

이는 7번부품 1개를 만들기 위해서는 5번 부품이 2개만큼 필요하다는 뜻이다.

그러면 리스트를 하나 더 만들어서 몇 번 부품이 몇개나 필요한지 써주자.

 

갯수 리스트를 EA_list로 명명하겠다. (기본으로 0이 들어가있는 1차원 배열에 길이는 N+1이다. )

EA_list의 j[0] ( 필요한 부품의 번호 ) 자리에, j[1] ( 부품의 갯수 ) * EA_list[i] (상위 부품의 갯수) 를 넣어준다.

 

(여기서 주의할 것이, EA 리스트의 초기 상태는 0이라는 것이다. 중간 부품이나 기본부품은 상위 부품에서 얼마나 필요한지를 받아오기 때문에 문제가 되지 않지만, 최종부품(맨 처음 시작하는 부품)은 0이기 때문에 이 때만 EA_list의 항목을 1로 바꿔줄 필요가 있다. 이는 나중에 코드시현에서 보여주겠다.)

 

이렇게하면, 최종부품(7번)을 만드는 데 필요한 5번 부품의 갯수를 EA_list에 기록하였다. 

그러면 우리는 7 -> 5를 지워줘야한다. 

 

i = 7, j = 0 에서 실행했을 경우

그러면 이제 parts_needed는 [0, 1, 1, 1, 2, 1, 1, 0] 이 된다. (idx 5 에서 하나 준 것에 주목하자.)

그리고 EA_list는 [0, 0, 0, 0, 0, 2, 0, 0] 이 된다. 최종 부품을 하나 만드는 데 5번이 2개 필요하다는 것이다.

 

이렇게 i = 7에서 j를 전부 진행하면

i = 7 에서 전부 진행했을 때,

7번에서 나가는 화살표가 모두 지워진 것을 알 수 있다.

parts_needed 는 [0, 1, 1, 1, 1, 1, 0, 0] 이 되고,

EA_list는 [0, 0, 0, 0, 5, 2, 3, 1]이 되었다.

(완제품을 만들기 위해서는 4번이 5개, 5번이 2개, 6번이 3개, 7번이 1개 필요하다는 뜻이다.)

 

 

그러면 이제 그 다음에 어떤 부품을 진행해야 되는지 보이지 않는가?

 

위의 그래프를 보자.

7번에서 향하는 화살표를 모두 지우니, 6번을 향하는 화살표가 사라진 것을 볼 수있다.

 

즉, 7번을 제외하면 6번이 최종 부품이 되는 것이다.

 

parts_needed에서도 6번자리가 0이 된 것을 알 수있다.. 그러면 다음은 i = 6에서 진행한다.

 

결국, parts_needed가 전부 0이 될 때까지 계속해서 반복해야할 것이며 (코드가 보인다!)

이 동안 for i in range(1,N+1)를 진행한다.

 

그런데 여기서 의문이 든다. 

 

"i = 7에서 진행하고, 다시 i를 처음부터 돌려 parts_needed = 0 인 6을 찾아서 i =6에서 진행한다고 쳐요.

그럼, i = 6이 끝나면, 그 다음엔 i가 7이니깐 또 i=7에서 수행하지 않을까요?"

 

그렇다. 그래서 우리는 한번 수행한 i에 대해서는 다시 수행하지 않도록 하기 위해서 방문기록을 남겨야한다.

 

그리고 이왕에 i를 1부터 N+1까지 돌리는 김에 기본 부품도 찾아보자.

(어떻게 찾는지는 위에서 설명했다.)

 

visited = [0]*(N+1)
basic = []

while sum(parts_needed) > 0:
    for i in range(1,N+1):
        if not need_parts[i] and visited[i] == 0:
            basic.append(i)
            visited[i] = 1
        if parts_needed[i] == 0 and visited[i] == 0:
            if EA_list[i] == 0:
                EA_list[i] = 1
            visited[i] = 1
            for j in need_parts[i]:
                EA_list[j[0]] += j[1]*EA_list[i]
                parts_needed[j[0]] -= 1

이 과정을 전부 수행하면 parts_needed와 EA_list는 다음과 같다.

 

최종부품에서 화살표를 지우면서 내려갔기 때문에 parts_needed가 전부 0이 된 것을 확인할 수 있다.

또한, EA_list는 이 장난감 한개를 만들기 위해서 각 부품이 몇개나 필요한지 알려주고 있다.

 

우리는 for문을 돌릴 때, need_parts가 비어있는 곳 (다른 부품을 요구하지 않는다는 뜻) 을 기본 부품으로 추가했기에 

basic = [1, 2, 3, 4]가 된다.

 

이 basic으로 기본부품이 몇개나 필요한지 출력해보자.

for i in basic:
    print(i, EA_list[i], sep=" ")

정답이다연금술사

1번 16개, 2번 16개, 3번 9개, 4번 17개가 필요하다는 것을 알 수있다.

 

전체 코드는 다음과 같다.

import sys
from collections import deque

sys.stdin = open("input.txt", "r")

N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())

need_parts = [[] for row in range(N+1)]
parts_needed = [0]*(N+1)
EA_list = [0]*(N+1)
visited = [0]*(N+1)
basic = []

for m in range(M):
    x, y, EA = map(int,sys.stdin.readline().split())
    need_parts[x].append([y,EA])
    parts_needed[y] += 1

while sum(parts_needed) > 0:

    for i in range(1,N+1):
        if not need_parts[i] and visited[i] == 0:
            basic.append(i)
            visited[i] = 1
      
        if parts_needed[i] == 0 and visited[i] == 0:
            if EA_list[i] == 0:
                EA_list[i] = 1
            visited[i] = 1

            for j in need_parts[i]:
                EA_list[j[0]] += j[1]*EA_list[i]
                parts_needed[j[0]] -= 1


for i in basic:
    print(i, EA_list[i], sep=" ")

 

 

이것이 indegree와 outdegree를 이용한 위상정렬 풀이법이었다.

 

처음에는 DFS로만 풀려고해서 힘들었는데, indegree와 outdegree로 푸니 코드도 깔끔해지고 결과도 굉장히 좋게 나왔다.

 

뿌듯