[백준] ACM Craft

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

1005번: ACM Craft

1. 문제 이해

스타크래프트처럼 건물 순서 규칙이 주어집니다. 그리고 건물을 지어지는데 소요시간이 걸리게 됩니다. 이 문제의 목표느는 건물 순서 규칙에 따라서 건물을 지었을 때 특정 건물을 짓는 데 걸리는 최소 시간을 구하는 문제입니다.

 

2. 문제 접근

첫번째 접근: 위상정렬

그래프가 단방향 간선으로 이루어져 있고 순서에 따라서 건물들이 지어져야하는 것을 보고 위상정렬을 떠올릴 수 있었습니다. 위상정렬을 진행하면서 (현재 건물이 지어지기 위해 필요한 건물들을 짓는데 필요한 시간 + 현재 건물을 짓는데 걸리는 시간)이 다음 건물이 지어지기 위해 필요한 최대시간을 갱신할 수 있는지를 체크해주면 됩니다.

 

3. 풀이

import sys, math
from collections import defaultdict, deque
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
T = int(input())

n, k, w = -1, -1, -1
delay = None
graph = None
in_node = None
time = None

for _ in range(T):
    n, k = tuple(map(int, input().split()))
    # 건물이 걸리는데 지어지는 시간
    delay = list(map(int, input().split()))
    graph = defaultdict(list)
    in_node = [0 for _ in range(n)]
    # 해당 건물이 가장 빠르게 지어질 수 있는 시간
    time = [0 for _ in range(n)]

    for _ in range(k):
        a, b = tuple(map(int, input().split()))

        a -= 1
        b -= 1

        graph[a].append(b)
        in_node[b] += 1

    w = int(input())
    w -= 1

    q = deque()

    for i in range(n):
        if in_node[i] == 0:
            q.append(i)

    while q:
        cur = q.popleft()

        for next in graph[cur]:
            # 다음 건물을 짓기 위해서는 현재 건물이 지어질 수 있기 위해 필요한 시간 + 현재 건물을 짓는 시간이다.
            time[next] = max(time[cur] + delay[cur], time[next])

            in_node[next] -= 1

            if in_node[next] == 0:
                q.append(next)

    print(time[w] + delay[w])

4. 회고

단방향, 건물의 순서를 보고 빠르게 캐치하여 어렵지 않게 풀이할 수 있었습니다.