[백준] 1005 - ACM Craft

1. 문제

1005번: ACM Craft

2. 개요

ACM Craft라는 게임이 있다.

이 게임에서 어떤 건물을 짓기 위해서는 다른 건물의 건설이 필요한 경우가 있다.

모든 건물의 건설에 걸리는 시간과, 건설 규칙이 주어졌을 때 어떤 건물을 짓기 위해서 걸리는 최소시간을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

목표 건물 W를 루트로 하고, 필요한 선행 건물들을 자식으로 하는 트리를 만들었을 때, 가장 먼 거리의 리프노드까지의 거리가 정답이 된다.

그래프를 역순으로 만들고 이를 바탕으로 최대비용을 구하기 위해 다익스트라를 활용한다.

3-2. Python

import sys
from collections import deque

T = int(sys.stdin.readline())

for t in range(T):    
    N, K = map(int, sys.stdin.readline().split())

    graph = [[] for i in range(N+1)]
    times = list(map(int, sys.stdin.readline().split()))
    elapsedTime = [0 for i in range(N+1)]
    finish = []

    answer = 0

    for k in range(K):
        X, Y = map(int, sys.stdin.readline().split())

        graph[Y].append(X)

    W = int(sys.stdin.readline())
    elapsedTime[W] = times[W-1]

    q = deque([W])
    
    while q:
        now = q.popleft()
        
        if graph[now]:
            for nextV in graph[now]:
                if elapsedTime[nextV] < elapsedTime[now] + times[nextV - 1]:
                    elapsedTime[nextV] = elapsedTime[now] + times[nextV - 1]

                    q.append(nextV)

        else:
            finish.append(now)

    longest = 0
    for i in range(len(finish)):
        if elapsedTime[finish[i]] > longest:
            longest = elapsedTime[finish[i]]

    print(longest)

3-3. C#

namespace boj_1005
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int T = int.Parse(Console.ReadLine());

            for (int t = 0; t < T; t++)
            {
                string[] input1 = Console.ReadLine().Split();
                int N = int.Parse(input1[0]);
                int K = int.Parse(input1[1]);

                List<List<int>> graph = new List<List<int>>();

                for (int i = 0; i < N + 1; i++)
                    graph.Add(new List<int>());

                List<int> finish = new List<int>();
                int[] times = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int[] elapsedTime = new int[N + 1];
                
                for (int k = 0; k < K; k++)
                {
                    string[] input2 = Console.ReadLine().Split();
                    graph[int.Parse(input2[1])].Add(int.Parse(input2[0]));
                }

                int W = int.Parse(Console.ReadLine());
                elapsedTime[W] = times[W - 1];

                Queue<int> q = new Queue<int>();
                q.Enqueue(W);

                while (q.Count > 0)
                {
                    int now = q.Dequeue();

                    if (graph[now].Count > 0)
                    {
                        foreach (int next in graph[now])
                        {
                            if (elapsedTime[next] < elapsedTime[now] + times[next - 1])
                            {
                                elapsedTime[next] = elapsedTime[now] + times[next - 1];
                                q.Enqueue(next);
                            }
                                
                        }
                    }

                    else
                    {
                        finish.Add(now);
                    }
                }

                int longest = 0;
                foreach (int f in finish)
                {
                    if (longest < elapsedTime[f])
                        longest = elapsedTime[f];
                }

                Console.WriteLine(longest);
            }
        }
    }
}