[BOJ 1005] ACM Craft - JAVA, Gold3

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

1005번: ACM Craft

사용한 알고리즘 : 위상정렬(Topological Sorting)

 

풀이전략

문제들을 주어진 이전 단계를 거쳐가야만 풀 수 있으므로 위상 정렬 알고리즘을 사용해야한다.

https://chaechaeros.tistory.com/199

[BOJ 1766] 문제집 - JAVA, Gold2

위상 정렬 알고리즘에 대해서 개념이 필요하면 위 링크를 참조하길 바란다.

 

단, 기본 적인 위상정렬 알고리즘을 사용하되 특정 건물을 짓는데 가장 최소한의 시간을 알아내는 것이

문제의 목표다.

 

주의할 점은 동시에 여러 개의 건물을 무제한으로 지을 수 있다는 점이다.

 

만약 위 주의점을 생각하지 않고 위상정렬 알고리즘을 그대로 적용시켜 건설 시간을 더해간다면

동시에 건물을 하나만 지을 수 있는 상태에서의 시간 총합이 계산될 것이다.

이를 해결하기 위한 계산법은 아래와 같다.

 

resultSum[x]를 노드 x를 짓는데 최소로 걸리는 시간의 총합,

cost[x]를 노드 x를 짓는데 걸리는 시간 이라고하면

아래 주어진 그래프의 각 노드에서 해당 노드를 짓기까지의 최소한의 시간을 아래 수식으로

구할 수 있다.

시작 노드부터 차례로 시작하여 각 노드 마다의 최소 시간 총합을 계산해 나간다.

 

위 그래프에서 7번 노드를 주의해서 보아야하는데,

만약 특정 노드의 이전 노드가 2개 이상인 경우에는

이전 모든 노드에 대하여 resultSum을 각각 계산해보고 그 중 가장 큰 값을 채택한다.

 

그래야 7번 이전 노드인 5, 6번 노드가 둘 다 지어진 상태에서 7번 노드가 지어질 수 있기 떄문이다.

(위상정렬에서는 진입차수가 0인 경우에 해당 노드에 대한 연산을 수행할 수 있기 때문이다.)

 

이를 코드로 나타내면 아래와 같다.

제출코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,K;
    static int graph[];
    static int indegree[];
    static int result[];
    static ArrayList<ArrayList<Integer>> list;

    static void topology(int objective){
        Queue<Integer> q = new LinkedList<>();
        for(int i=1;i<=N;++i){
            if(indegree[i]==0) q.offer(i);
        }

        while(!q.isEmpty()){
            int now = q.poll();
            for(int x:list.get(now)){
                --indegree[x];
                if(indegree[x]==0){
                    q.offer(x);
                }
                result[x]=Math.max(result[x],result[now]+graph[x]);
            }
        }
    }
    public static void main(String argsp[]) 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());
        for(int t=0;t<T;++t){
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            list = new ArrayList<>();
            list.add(new ArrayList<>());

            graph = new int[N+1];
            indegree = new int[N+1];
            result = new int[N+1];
            st=new StringTokenizer(br.readLine());
            for(int i=1;i<=N;++i){
                graph[i]=Integer.parseInt(st.nextToken());
                list.add(new ArrayList<>());
                result[i]=graph[i];
            }
            for(int i=0;i<K;++i){
                st=new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                list.get(a).add(b);
                ++indegree[b];
            }

            int victoryBuilding = Integer.parseInt(br.readLine());
            topology(victoryBuilding);
            bw.write(result[victoryBuilding]+"\n");
        }
        bw.flush();
        bw.close();
    }
}