[파이썬] [그래프] 백준 1005 ACM Craft

문제

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

1005번: ACM Craft

코드

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

t=int(input())
for _ in range(t):
    n,k=map(int, input().split())
    graph=[[] for _ in range(n+1)]
    time=[0]+list(map(int, input().split()))
    indegree=[0]*(n+1)
    for _ in range(k):
        a,b=map(int, input().split())
        graph[a].append(b)
        indegree[b]+=1
    w=int(input())

    dp=[0]*(n+1)
    queue=deque()

    for i in range(1,n+1):
        if indegree[i]==0:
            queue.append(i)
            dp[i]=time[i]
    while queue:
        cur=queue.popleft()
        for i in graph[cur]:
            indegree[i]-=1
            dp[i] =max(dp[i], dp[cur]+time[i])
            if indegree[i]==0:
                queue.append(i)

        if indegree[w]==0:
            print(dp[w])
            break

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

public class Main
{
    static int n;
    static int k;
    static int[] cost;
    
	public static void main(String[] args) throws Exception {
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int tc=Integer.parseInt(br.readLine());
        for (int t=0; t<tc; t++){
            st = new StringTokenizer(br.readLine());
            n=Integer.parseInt(st.nextToken());
            k=Integer.parseInt(st.nextToken());
        
            cost = new int[n+1];
            st = new StringTokenizer(br.readLine());
            for(int i=1; i<n+1; i++){
                cost[i]=Integer.parseInt(st.nextToken());
            }
            
            List<List<Integer>> graph=new ArrayList<>();
            for(int i=0; i<n+1; i++){
                graph.add(new ArrayList<Integer>());
            }
            
            int[] indegree = new int[n+1];
            for (int i=0; i<k; i++){
                st=new StringTokenizer(br.readLine());
                int v1=Integer.parseInt(st.nextToken());
                int v2=Integer.parseInt(st.nextToken());
                
                graph.get(v1).add(v2);
                indegree[v2]++;
            }
            
            int des = Integer.parseInt(br.readLine());
            
            topo(indegree,graph,des);
        }
	}
	static void topo(int[] indegree, List<List<Integer>> graph, int des){
	    Queue<Integer> q=new LinkedList<Integer>();
	    int[] dp=new int[n+1];
	    for (int i=1; i<=n; i++){
	        dp[i]=cost[i];
	        
	        if (indegree[i]==0){
	            q.add(i);
	        }
	    }
	    while(!q.isEmpty()){
	        int node = q.remove();
	        for(Integer i: graph.get(node)){
	            indegree[i]--;
	            dp[i]=Math.max(dp[i],dp[node]+cost[i]);
	            
	            if (indegree[i]==0){
	                q.add(i);
	            }
	        }
	    }
	    System.out.println(dp[des]);
	}
}