[BOJ 1005] ACM Craft (Java)

BOJ 1005 ACM Craft

난이도 : 골드 3

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

1005번: ACM Craft

 

전략

단순 위상정렬해서 순서만 중요한 것이 아니라

 

소요시간을 계산해야 한다.

 

이는 다음 노드 탐색 과정에서 메모이제이션을 이용하여 최댓값을 저장하는 방식을 사용했다.

 

단순히 값을 저장하면 되는 것처럼 보이지만, 여러 경로가 합쳐질 때는 최댓값을 이용하여야 결과를 얻을 수 있다.

 

시행착오

메모이제이션을 큐에서 꺼낸 위치에서 실행했는데, 이미 이전 노드 dp가 끝난 이후라서 틀린 결과가 나왔다.

 

따라서 큐에서 꺼낸 노드가 가리키는 노드들에 대해서 dp를 해줘야 한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T, N, K;
        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            String[] line = br.readLine().split(" ");
            N = Integer.parseInt(line[0]);
            K = Integer.parseInt(line[1]);

            Node[] nodes = new Node[N + 1];

            line = br.readLine().split(" ");
            for (int i = 1; i <= N; i++)
                nodes[i] = new Node(i, Integer.parseInt(line[i - 1]));

            for (int i = 0; i < K; i++) {
                line = br.readLine().split(" ");
                int from = Integer.parseInt(line[0]);
                int to = Integer.parseInt(line[1]);
                nodes[from].link.add(nodes[to]);
                nodes[to].linked++;
            }
            int dest = Integer.parseInt(br.readLine());
            System.out.println(topologySort(nodes, dest));
        }

        br.close();
    }

    static int topologySort(final Node[] nodes, int dest) {
        final int N = nodes.length - 1;
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n2.cost - n1.cost);
        int[] dp = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            dp[i] = nodes[i].cost;

            if (nodes[i].linked == 0)
                pq.offer(nodes[i]);
        }

        for (int i = 0; i < N; i++) {
            if (pq.isEmpty())
                break;

            Node cur = pq.poll();

            if (cur.num == dest)
                break;

            for (Node next : cur.link) {
                dp[next.num] = Math.max(dp[next.num], dp[cur.num] + next.cost);

                if (--next.linked == 0)
                    pq.offer(next);
            }
        }
        return dp[dest];
    }

    static class Node {
        int num;
        int cost;
        int linked = 0;
        ArrayList<Node> link = new ArrayList<>();
        Node(int num, int cost) {
            this.num = num;
            this.cost = cost;
        }
    }
}

 

깨달은 점

dp의 세계는 무궁무진한 것 같다.