Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

35. 위상 정렬

간선에 방향이 있는 그래프의 정점을 나열해 역방향이 없게 만드는 알고리즘을 다뤄 봅시다.

3. ACM Craft

1005번

위상정렬된 순서대로 동적 계획법을 적용하는 문제

이번 문제는, 요약하면, 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 문제이다.

따라서 이번 문제의 경우 위상 정렬을 할 때, 소요 시간을 기억하고 이용해야 한다. 이전 건물이 다 올라가야 현재 건물을 지을 수 있기 때문에 이전 건물까지의 소요시간과 현재 건물의 소요시간을 더하여 오래 걸리는 값으로 result를 갱신해준다. 건물 W를 건설완료 하는데 드는 최소 시간(result[w])을 출력한다.

Java / Python

• Java

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

public class Main {

	static int N, K;
	static int[] time;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());
		while (T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			time = new int[N + 1];

			ArrayList<Integer>[] list = new ArrayList[N];
			int[] indegree = new int[N + 1];
			st = new StringTokenizer(br.readLine());

			for (int i = 0; i < N; i++) {
				list[i] = new ArrayList<>();
				time[i] = Integer.parseInt(st.nextToken());
			}
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());

				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());

				list[s - 1].add(e - 1);
				indegree[e - 1]++;
			}

			int w = Integer.parseInt(br.readLine()); // 건물 번호 

			bw.write(topologicalSort(indegree, list, w) + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	public static int topologicalSort(int[] indegree, ArrayList<Integer>[] list, int w) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int[] result = new int[N + 1];

		// 건물 기본 소요시간
		for (int i = 0; i < N; i++) {
			if (indegree[i] == 0) {
				result[i] = time[i];
				queue.offer(i);
			}
		}

		// 총 소요시간 = 이전 건물까지의 소요시간 + 현재 건물 소요시간
		while (!queue.isEmpty()) {
			int node = queue.poll();
			for (int i : list[node]) {
				result[i] = Math.max(result[i], result[node] + time[i]);
				indegree[i]--;

				if (indegree[i] == 0)
					queue.offer(i);
			}
		}
		return result[w - 1];
	}
}

• Python

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N,K = map(int,input().split())
    time = [0]+list(map(int,input().split())) # 건설 시간
    tree = [[] for _ in range(N+1)]
    indegree=[0 for _ in range(N+1)]
    dp = [0 for _ in range(N+1)] # 해당 건물까지 걸리는 시간

    for _ in range(K): # 입력값 받기
        s, e = map(int,input().split())
        tree[s].append(e)
        indegree[e]+=1

    que = deque()
    for i in range(1,N+1):
        if indegree[i] == 0:
            que.append(i)
            dp[i] = time[i]

    while que:
        node = que.popleft()
        for i in tree[node]:
            indegree[i]-=1
            dp[i] = max(dp[node] + time[i], dp[i]) 
            if indegree[i] == 0:
                que.append(i)

    w = int(input())
    print(dp[w])