백준 | 장난감 조립 (2637) | 파이썬(Python)

백준 | 장난감 조립 (2637) | 파이썬(Python)

반응형

| 문제 해설

이번 문제 같은 경우는 노드간 방향이 정해져 있는 방향 그래프이고, 간선에 가중치가 주어진다. 그래서 인접리스트를 이용하여 직접 눈으로 확인하면서 문제를 풀어나갔다. 즉 위상 정렬을 이용하여 문제를 풀었고, 진입 차수가 없는 노드를 큐에 추가하고 차수를 -1 하고 차수가 0이 된 노드는 다시 큐로 추가하는 과정을 반복했다.

고려해야 할 포인트

부품 수와 간선 수, 노드별 연결 정보 입력값 저장 가중치를 입력할 2차원 배열을 생성

자연수 X, Y, K 의미: 중간 부품이나 완제품 X를 만드는데 중간 부품 혹은 기본부품 Y가 K개 필요 중간 부품이 서로를 필요로 하는 경우 없음

가중치를 고려해야 하는 문제는 처음이다 보니 문제를 어떻게 접근해야 할지 막막했다. 그래서 가중치를 입력한 행렬을 프린트 찍어가면서 계속 이해하려고 노력했다.

| 최종 코드

from collections import deque N, M = int(input()), int(input()) link = [[] for _ in range(N+1)] # 노드별 연결 정보 matrix = [[0]*(N+1) for _ in range(N+1)] # 가중치 입력 indegree = [0] * (N+1) # 진입 차수 for i in range(M): a, b, c = map(int, input().split()) link[b].append((a, c)) indegree[a] += 1 # 진입 차수가 없는 노드(기본 부품) 큐에 추가 que = deque() for i in range(1, N+1): if indegree[i] == 0: que.append(i) while que: now = que.popleft() # next: now를 재료로 사용하는 부품. needs: now의 개수 for next, needs in link[now]: # 진입 차수 없는 노드(기본 부품) if matrix[now].count(0) == N+1: matrix[next][now] += needs else: for i in range(1, N+1): # 중간부품 * 중간부품 필요 개수 matrix[next][i] += matrix[now][i] * needs indegree[next] -= 1 if indegree[next] == 0: que.append(next) # 진입차수 0개일시 큐에 추가 for i in enumerate(matrix[N]): if i[1] > 0: print(i[0], i[1])

코드 설명

가장 첫 줄에 주어지는 입력값 N은 완제품의 번호이고, 1~N-1번 까지는 N을 만들기 위해 필요한 기본 부품이나 중간 부품의 번호이다.

두번 째 줄에 주어지는 입력값 M은 노드별로 연결되어 있는 간선의 수이고, 세 번째 줄부터는 노드간 연결 정보 M개가 주어진다. 문제의 예제로 예를 들자면, 이것은 5번 부품을 만드는데 1번 부품 2개가 필요하다는 말이다. 즉 1번 노드에서 5번 노드로 향하는 진입 차수가 주어지고, 그 간선에 2라는 가중치가 부여된다.

5 1 2

이것은 5번 부품을 만드는데 1번 부품 2개가 필요하다는 말이다. 즉 1번 노드에서 5번 노드로 향하는 진입 차수가 주어지고, 그 간선에 2라는 가중치가 부여된다.

가중치를 입력할 배열(matrix)과 진입 차수를 저장할 리스트(indegree)를 생성한다. 이 때, 0번 부품은 존재하지 않기 때문에 범위를 N-1까지 설정한다.

가중치를 넣지 않은 상태의 인접리스트(matrix) 세 번째 줄부터 주어지는 입력값을 받을 때, 노드별 연결 정보를 저장하는 link라는 변수에 인덱스 값, 즉 주어진 입력값 중 두 번째에 해당하는 원소가 리스트의 인덱스로 들어가게 하고, 첫 번째와 세 번째 변수는 두 번째 원소 인덱스의 값에 포함되도록 추가한다.

for i in range(M): a, b, c = map(int, input().split()) link[b].append((a, c)) indegree[a] += 1​ 진입 차수가 없는 노드는 큐에 추가하도록 한다. 진입 차수가 없다는 것은 문제에서 기본 부품에 해당한다는 것과 같은 의미이다.

큐에 쌓인 원소들을 popleft()를 통해 하나씩 빼면서 연결을 해제하고, 팝한 노드가 기본 부품이면 가중치 배열에 바로 추가, 중간 부품이면 필요한 중간 부품의 수 * 가중치를 연산한 후 배열에 추가한다. 가중치를 배열에 추가한 후, 해당되는 진입 차수를 -1 한다. 큐가 빌 때까지 반복문을 돌리면 가중치 그래프는 다음과 같이 채워진다.

코드로 구현하는 과정에서 많이 헷갈리지만, 현재 now변수가 몇 번째 인덱스인지, for문에서 next가 몇 번째 인덱스인지 등을 matrix 배열을 보면서 코드를 작성한다면 더 이해하기 쉬울 것 같다.

| 공부한 내용 정리

enumerate

반복문 사용 시 몇 번째 반복문인지 확인할 수 있는 기능으로, 인덱스 번호와 iterable 객체를 같이 출력한다. 이때, 튜플 형식으로 (인덱스, 객체)와 같은 방식으로 출력한다. 위의 matrix를 예시로 하면 이렇다.

튜플 형식으로 첫 번째 인자에는 인덱스, 다음에는 이터럴의 객체가 출력된다.

* 레퍼런스

https://velog.io/@qweadzs/BOJ-2637-%EC%9E%A5%EB%82%9C%EA%B0%90-%EC%A1%B0%EB%A6%BDPython

반응형

from http://dapsu-startup.tistory.com/52 by ccl(A) rewrite - 2021-08-23 22:26:10