[python] Baekjoon 1005 : ACM Craft

문제 - Baekjoon 1005 : ACM Craft

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

1005번: ACM Craft

핵심

최소 시간 내 건물 완성 알고리즘

내용

이 문제는 건물 건설 순서를 고려하여 특정 건물을 완성하는 데 필요한 최소 시간을 찾는 과제입니다. 각 건물은 독립적인 건설 시간을 가지며, 일부 건물은 다른 건물들이 완성된 후에만 건설할 수 있습니다. 이 문제는 효율적인 알고리즘 설계와 자료 구조의 이해를 요구합니다.

ACM Craft

접근 방법

이 문제는 Directed Acyclic Graph (DAG)를 이용한 동적 프로그래밍 문제입니다. DAG에서 각 건물은 노드로, 건설 순서는 방향성이 있는 간선으로 표현됩니다. 이를 통해 각 건물을 지을 수 있는 최소 시간을 계산할 수 있습니다.

1. 각 건물을 노드로 갖는 DAG 생성
2. Topological Sorting을 사용하여 건물들의 건설 순서를 결정
3. 각 노드(건물)에 대해, 그 건물을 지을 수 있는 최소 시간을 동적 프로그래밍을 통해 계산

->  main point

1. 입력 파싱: 먼저, 입력 데이터를 적절하게 파싱하여 문제에 필요한 정보(건물의 수, 규칙, 건설 시간 등)를 추출합니다.
2. 위상 정렬(Topological Sorting): 건물들 사이의 의존성을 고려하여, 어떤 순서로 건물들을 건설해야 하는지 결정합니다. 이를 위해 각 건물의 진입 차수를 계산하고, 진입 차수가 0인 건물부터 처리합니다.
3. 동적 계획법(Dynamic Programming, DP): 각 건물을 완성하는데 걸리는 최소 시간을 계산하기 위해 DP를 사용합니다. 이는 각 건물을 짓기 시작할 수 있는 최소 시작 시간을 계산하는 것을 포함합니다.

코드

from collections import deque
import sys

def find_min_time(build_times, rules, target):
    n = len(build_times)
    indegree = [0] * (n + 1)
    graph = [[] for _ in range(n + 1)]
    dp = [0] * (n + 1)

    for x, y in rules:
        graph[x].append(y)
        indegree[y] += 1

    q = deque()
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append(i)
            dp[i] = build_times[i - 1]

    while q:
        current = q.popleft()
        for next_node in graph[current]:
            indegree[next_node] -= 1
            dp[next_node] = max(dp[next_node], dp[current] + build_times[next_node - 1])
            if indegree[next_node] == 0:
                q.append(next_node)

    return dp[target]

def main():
    input_data = sys.stdin.readlines()
    idx = 0
    t = int(input_data[idx].strip())  # 첫 줄에 테스트 케이스의 수
    idx += 1

    for _ in range(t):
        n, k = map(int, input_data[idx].split())
        idx += 1
        build_times = list(map(int, input_data[idx].split()))
        idx += 1

        rules = []
        for _ in range(k):
            x, y = map(int, input_data[idx].split())
            rules.append((x, y))
            idx += 1

        target = int(input_data[idx].strip())
        idx += 1

        print(find_min_time(build_times, rules, target))

if __name__ == "__main__":
    main()

풀이

이 코드는 먼저 입력된 건물 건설 시간과 규칙을 바탕으로 DAG를 구성합니다. 그 후 Topological Sorting을 사용하여 건물들의 건설 순서를 결정하고, 각 건물을 지을 수 있는 최소 시간을 계산합니다. 최종적으로 타겟 건물을 지을 수 있는 최소 시간을 반환합니다.

 

1. 입력 파싱:
   • t (테스트 케이스의 수), n (건물의 수), k (규칙의 수)를 파싱합니다.
   • 각 건물을 짓는 데 필요한 시간(build_times)과 건물 간의 의존성 규칙(rules)을 파싱합니다.
2. 위상 정렬 실행:
   • 각 건물의 진입 차수(indegree)와 의존성 그래프(graph)를 초기화합니다.
   • rules를 통해 그래프를 구성하고, 각 건물의 진입 차수를 업데이트합니다.
   • 진입 차수가 0인 모든 노드를 큐에 넣습니다.
3. 동적 계획법 적용:
   • 큐에서 건물을 하나씩 꺼내면서, 해당 건물을 지을 수 있는 최소 시작 시간(dp)을 갱신합니다.
   • 각 후속 건물에 대해 최소 시작 시간을 업데이트하고, 해당 건물의 진입 차수를 감소시킵니다.
   • 진입 차수가 0이 되는 건물을 큐에 추가합니다.
4. 결과 출력:
   • 각 테스트 케이스에 대해, 목표 건물(target)을 짓기 위한 최소 시간을 dp[target]에서 조회하고 출력합니다.

python

참고 자료

- DAG와 Topological Sorting에 대한 개념: [GeeksforGeeks](https://www.geeksforgeeks.org/topological-sorting/))
- Python의 deque 사용법: [Python 공식 문서](https://docs.python.org/3/library/collections.html#collections.deque))
- 동적 프로그래밍 기법: [Introduction to Dynamic Programming](https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews))

- 위상 정렬(Topological Sorting): 위상 정렬에 대한 이해를 돕기 위한 GeeksforGeeks 자료.