Q1005 ACM Craft

위상정렬 이라는 개념을 알아야 한다고 한다.

 

모르고 처음 푼 코드를 올린다.

 

그냥 dfs로 스택에 담아서 쭉 둘러보는 방법으로 옛날에 dfs풀었던 방법을 적용해서 풀었다.

 

분명 기존알고리즘과는 다르기때문에 비효율적으로 짰을 것이다.

 

 

 

 

4를 짓기 위해선 2,3을 동시에 행할 수 있고, 3을 건설하는 동안 2는 이미 다 완성되어 결과에 영향을 미치지 않는다.

 

4를 지으려면 10+100+10 = 120초의 건설시간 필요

 

만약 

 

이렇게 되어있고 4가 최종건물이라면

 

4에서 바라봤을때 2,3,5가 지어져야 하는데 어차피 5가 110초이므로 2,3은 볼 필요도 없다.

 

그러므로 5가 최종 건설시간이다. 라고 생각할 수도 있다. 

 

2,3이 결과에 무의미하다 해서 넘어가서는 안된다. 1때문에

 

그래서 모든 노드를 한번은 탐색해서 모든 상황의 시간체크가 필요하다.

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    public static HashMap<Integer, node> nodes = new HashMap<Integer, node>();
    public static Stack<Integer> stack = new Stack<Integer>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        int testCase = Integer.parseInt(st.nextToken());
        
        for (int x = 0; x < testCase; x++) {
            nodes = new HashMap<Integer, node>();    
            st = new StringTokenizer(br.readLine());
            int nodeSize = Integer.parseInt(st.nextToken());
            int ruleSize = Integer.parseInt(st.nextToken());
 
            st = new StringTokenizer(br.readLine());
            for(int y = 1; y <= nodeSize; y++) {
                nodes.put(y, new node());
                nodes.get(y).buildingTime = Integer.parseInt(st.nextToken());
            }
 
            for(int y = 0; y < ruleSize; y++) {
                st = new StringTokenizer(br.readLine());
                int first = Integer.parseInt(st.nextToken());
                int second = Integer.parseInt(st.nextToken());
                nodes.get(first).out.add(second);
                nodes.get(second).in.add(first);
            }
            
            int start = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
            stack.push(start);
            int current;
            node node;
            int currNodeRequireTime;
            int currNodeBuildTime;
            int currentRequireTime;
 
            while (!stack.isEmpty()) {
                current = stack.peek();
                node = nodes.get(current);
                if (node.in.size() != 0) {
                    current = node.in.get(0);
                    stack.push(current);
                } else {
                    stack.pop();
                    node = nodes.get(current);
                    for (int i = 0; i < node.out.size(); i++) {
                        currNodeRequireTime = nodes.get(current).prerequisiteTime;
                        currNodeBuildTime = nodes.get(current).buildingTime;
                        currentRequireTime = nodes.get(node.out.get(i)).prerequisiteTime;
                        if (currentRequireTime < (currNodeRequireTime + currNodeBuildTime)) {
                            nodes.get(node.out.get(i)).prerequisiteTime = (currNodeRequireTime + currNodeBuildTime);
                        }
                        node tempNode = nodes.get(node.out.get(i));
                        for (int j = 0; j < tempNode.in.size(); j++) {
                            if (tempNode.in.get(j) == current) {
                                tempNode.in.remove(j);
                                break;
                            }
                        }
                    }
                }
            }
            System.out.println(nodes.get(start).prerequisiteTime + nodes.get(start).buildingTime);
        }
    }
 
    public static class node {
 
        public int buildingTime;
        public ArrayList<Integer> in;
        public ArrayList<Integer> out;
        public ArrayList<Integer> needBuildingNode;
        public int prerequisiteTime; // 이 건물을 짓기위한 사전필요시간(자기자신 제외)
 
        node() {
            in = new ArrayList<Integer>();
            out = new ArrayList<Integer>();
            needBuildingNode = new ArrayList<Integer>();
            prerequisiteTime = 0;
        }
    }
 
}