문제 풀이(7)

https://www.acmicpc.net/problem/2637

import java.io.*;
import java.util.*;

/**
 * Solution
 */
class Node{
	int number ;

	int value ;

	Node(int number , int value)
	{
		this.number = number;
		this.value = value;
	}
}

public class Solution {

	static ArrayList<Node>[] adj ;

	static int[] indegree;

	static int[][] matrix;
	public static void main(String[] args) throws IOException {
		BufferedReader br = 
		new BufferedReader(new InputStreamReader(System.in));
	
		int N = Integer.parseInt(br.readLine());

		matrix = new int[N + 1][N + 1];
	
		adj = new ArrayList[N + 1];

		indegree = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			adj[i] = new ArrayList<>();
		}

		int M = Integer.parseInt(br.readLine());

		for (int i = 0; i < M; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());

			int y = Integer.parseInt(st.nextToken());

			int k = Integer.parseInt(st.nextToken());

			adj[y].add(new Node(x, k));			

			indegree[x]++;
		}

		Queue<Integer>Q = new LinkedList<>();

		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) {
				Q.offer(i);
				matrix[i][i] = 1;
			}
		}

	

		
		while (!Q.isEmpty()) {
			
			int now = Q.poll();


			for(Node node : adj[now])
			{
				int next = node.number;

				int cost = node.value;

				indegree[next]--;

				if (indegree[next] == 0) {
					Q.offer(next);
				}

				for (int i = 1; i <= N; i++) {
		            matrix[i][next] = 
					matrix[i][next] + (matrix[i][now] * cost);
				}
			}
		}


		for (int i = 1; i <= N; i++) {
			
			if(matrix[i][N] != 0) System.out.println(i+" "+matrix[i][N]);

		}

	}
}

노드의 개수 N을 입력받는다.matrix 배열과 adj 배열을 초기화한다. matrix 배열은 동적 프로그래밍을 위한 배열로, matrix[i][j]는 노드 i에서 노드 j로 가는 경로의 수를 의미한다.adj 배열은 각 노드마다 연결된 노드와 가중치를 저장하는 리스트의 배열이다.indegree 배열은 노드의 진입 차수를 저장한다. 간선의 개수 M을 입력받는다.M번 반복하면서 각 간선 정보를 입력받고, adj 배열에 연결 정보와 가중치를 추가하고 진입 차수를 증가시킨다.모든 진입 차수가 0인 노드를 큐에 넣어 위상 정렬을 시작한다.
큐에서 노드를 하나씩 꺼내면서 해당 노드에서 출발하는 간선을 확인하고 진입 차수를 감소시킨다.진입 차수가 0이 되는 노드를 큐에 넣으면서, 해당 노드로 가는 경로 수를 동적 프로그래밍 배열인 matrix에 업데이트한다.
이때, matrix[i][next] 값은 matrix[i][now] * cost로 계산된다. 이는 현재까지의 경로 수에 해당 간선의 가중치를 곱하여 다음 노드까지의 경로 수를 구하는 것이다.
모든 노드에 대해 matrix[i][N] 값을 출력한다. 이 값은 노드 i에서 노드 N까지의 경로 수를 나타낸다.