[백준] 2637 장난감 조립 풀이 Java, 위상 정렬

 

2637번: 장난감 조립

★ 위상 정렬(Topological Sort)을 잘 모르면 아래 게시글을 보고 오는걸 추천드립니다.

 

위상 정렬(Topological sort) BFS,DFS

 

위 포스팅에 있는 위상 정렬 개념을 이용하면 풀리는 문제이다.

 

• 포인트 1

헷갈렸던 포인트가 있는데, 이 문제에서는 여러 부품을 조립해서 완제품을 생성한다.

그렇게 되면 여러 부품 -> 완제품 화살표가 만들어져서 완제품의 부품의 in-degree 값이 증가해야 한다.

왜냐하면 in-degree는 '특정 노드로 들어오는 간선의 개수' 이기 때문이다.

 

하지만 이 문제에서는 거꾸로 특정 노드의 in-degree 값을 증가시킨다.

개념에 따르면 outdegree라고도 할 수 있는데.. BFS 로 풀기 위해선 in-degree 값이 있어야 하기 때문에 반대로 두고 적용한다.

 

완제품 -> 부품C -> 부품B -> 부품A

위처럼 진행되기 때문에 in-degree가 0인 node를 넣으며 시작하는 과정에서

완제품의 노드가 Queue에 들어가고 로직이 진행된다.

 

이 부분만 이해하면 위상정렬을 그대로 적용했다고 생각하면 된다.

 

• 포인트 2

이 문제에선 크게 4가지 정보를 저장한다.

arr - 실제 답이 담겨있는 배열로 완제품을 생산하기 위해서 각 부품이 몇 개씩 사용되어야 하는지 나타낸다.

in - indegree로 위에서 설명한것과 같다. 이 문제에서는 개념적으로는 outdegree에 가까운 값을 가지고 있다.

dag - dag를 생성하며, 몇 개의 부품이 필요한지 가중치도 함께 저장한다.

isComb - 중간부품인지(true) 기본부품인지(false) 를 판단한다. isComb가 false인 경우에만 답으로 출력한다.

 

• 포인트 3

arr[i] += arr[node] * dag[node][i];

node는 현재 부품이고 i는 이 부품을 생성하기 위한 부품이다. (여러개의 i로 node를 생성)

 

 

import java.util.*;

public class Main {
	static int n;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		n = scan.nextInt();
		int m = scan.nextInt();

		int[] arr = new int[n + 1];
		int[] in = new int[n + 1];
		int[][] dag = new int[n + 1][n + 1];
		boolean[] isComb = new boolean[n + 1];

		for (int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();

			dag[a][b] = scan.nextInt();
			in[b]++;
			isComb[a] = true;
		}

		Queue q = new LinkedList<>();

		for (int i = 1; i <= n; i++) {
			if (in[i] == 0) {
				q.add(i);
				arr[i] = 1;
			}
		}

		while (!q.isEmpty()) {
			int node = (int) q.poll();

			for (int i = 1; i <= n; i++) {
				if (dag[node][i] != 0) {
					arr[i] += arr[node] * dag[node][i];
					in[i]--;

					if (in[i] == 0)
						q.add(i);
				}
			}
		}

		// print
		for (int i = 1; i <= n; i++) {
			if (!isComb[i])
				System.out.print(i + " " + arr[i] + "\n");
		}

	}
}