[백준 알고리즘: python 3] #1005 - ACM Craft

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

 

읽기 전에! 혹시 시간초과이신가요..?

시간초과로 여러번 실패했던 문제입니다. 첫 제출의 코드 내용은 틀린 내용이 없었는데, 시간초과 때문에 코드도 싹 바꿔보고 했었습니다. 아무리 생각을 해봐도 이렇게 했는데 시간초과인거면 그냥 파이썬으로 못푸는건가...? 라는 이상한 생각도 해봤습니다. 결론만 말씀드리면, 이 문제처럼 input의 양이 많을 경우 input() 대신 sys.stdin.readline()을, print() 대신 sys.stdout.write() 을 대체하여 사용하면 러닝 타임이 매우!! 많이!! 빨라진다고 합니다. 저도 처음 알았는데 기존 python의 input(), print() 함수는 호출이 느리다고 하네요.. 저도 이 부분만을 수정해서 시간초과를 해결했습니다... 어이없어 아무튼! 자신의 알고리즘에 문제가 없는 것 같은데 시간 초과로 괴로워 하고 있다면 우선 위와 같이 수정해보고 다시 제출해보시기를 권장드립니다.

 

1005번은 ACM craft라는 건물을 짓는 순서와 시간이 주어졌을 때, 목표 건물을 짓는데 걸리는 가장 짧은 시간을 구하는 문제입니다. 스타크래프트를 해보신 분이라면 잘 이해가 가실 것 같습니다.

ACM Craft 예시

위의 사진과 같은 건설 맵이 그려질 경우에,

 

1. 1번 건물의 건설이 시작된다. (0초 경과)
2. 10초 후, 1번 건물이 완성된다. (1 완료, 10초 경과)
3. 2, 3번 건물의 건설이 동시에 시작된다. (1 완료, 10초 경과)
4. 1초 후, 2번 건물이 완성된다. (1, 2 완료, 11초 경과)
5. 109초 후, 3번 건물이 완성된다. (1, 2, 3 완료, 110초 경과)
6. 4번 건물의 건설이 시작된다. (1, 2, 3 완료, 110초 경과)
7. 10초 후, 4번 건물이 완성된다. (1, 2, 3, 4 완료, 120초 경과)

 

이렇게 총 120초의 시간이 흐르면 4번 건물을 완성할 수 있다는 것을 확인할 수 있습니다. 

 

Hint!

위의 순서 설명에서 보면 알 수 있지만 저는 건설이 시작된 건물의 잔여 건설 시간 중 최소시간을 한 스텝으로 두고 풀이하였습니다.

 

1. 진입 차수가 0(초기 건물이라 이해하시면 될 것 같습니다.)인 모든 건물의 건설을 시작한다.
2. 건설 중인 모든 건물의 잔여 건설 시간 중, 최소 시간을 뽑는다. (위의 4번 참고)
3. 최소 시간을 총 시간에 누적 시킨 뒤, 건설 중인 모든 건물의 잔여 건설 시간에 최소시간을 모두 뺀다. (최소 시간이 흐른 뒤 상황을 의미)
4. 잔여 시간이 0인 건물은 완성된 건물이고, 이 건물이 완료되어 시작할 수 있는 모든 건물의 건설을 시작한다.
5. 2~4번을 목표 건물이 완성될 때까지 반복한다.

 

이렇게 하기 위해서 세가지가 필요하다고 생각했습니다.

 

1. 각 건물의 잔여 시간을 기록하는 dict (operating_map)
   1. ex) operating_map = {1: 10, 2: 1, 3: 100, 4: 10}
   2. 이 변수는 매 최소시간이 흐를 때마다 갱신되고, value가 0이 되면 완성된 건물로 판단합니다.
2. 진입차수가 0인 건물과 선행 건물이 요구되는 건물들의 정보가 저장된 dict(rule_map)
   1. ex) rule_map = {1: set(), 2: {1}, 3: {1}, 4: {2, 3}}
   2. 1번 건물은 선행 건물이 없으므로, 초기 건물로 생각할 수 있습니다.
   3. 이 변수는 매 건물이 완성이 될 때마다, 완성된 건물의 set이 남은 건물들의 선행 건물 set을 포함하고 있을 때 그 건물은 건설시작이 가능함을 알려줄 수 있습니다. 예를 들면, 현재 완성된 건물이 {1, 2, 3}인 경우, 남은 건물인 4번 건물의 선행 건물이 {2, 3} 이므로 이 집합은 {1, 2, 3}에 포함됩니다. 즉, 4번 건물은 건설 시작이 가능합니다.
3. 기타 현재 상황을 표시해 줄 변수들
   1. 현재 건설 중인 건물 set, 여기서 operating_map을 통해 이 건물들의 잔여 시간에서 최소시간을 뽑습니다.
   2. 완성된 건물 set, 이것으로 rule_map을 통해 이제 건설이 가능한 건물을 알아냅니다.
   3. 총 시간 int, 1에서 구한 최소 시간을 계속 누적합니다.

 

이 내용을 바탕으로 아래와 같은 코드를 작성하여 성공하였습니다.

 

import sys
T = int(sys.stdin.readline())
results = []

for _ in range(T):
    N, K = map(int, sys.stdin.readline().split())
    D = list(map(int, sys.stdin.readline().split()))
    R = []
    for _ in range(K):
        X, Y = map(int, sys.stdin.readline().split())
        R.append([X, Y])
    W = int(sys.stdin.readline())

    # 잔여 시간 정보
    operating_map = {}
    for building, time in enumerate(D):
        operating_map[building+1] = time

    # 각 건물의 선행 건물에 대한 정보
    rule_map = {}
    for i in range(N):
        rule_map[i+1] = set()
    for rule in R:
        X = rule[0]
        Y = rule[1]
        rule_map[Y].add(X)

    # 완성된 건물
    done = set()
    time = 0
    
    # 목표 건물 W 가 완료된 건물에 포함될 때까지,
    while W not in done:
        # 건설 진행 중인 건물들
        bases = []
        for building in rule_map:
            # 잔여 건물 중, 선행 건물들이 모두 완료되었을 경우 건설 중인 건물에 추가.
            if done.issuperset(rule_map[building]) and building not in done: 
                bases.append(building)
        
        # 건설 중인 건물 중 잔여 최소 시간 계산 후, 총 시간(time)에 더함.
        time_step = min([operating_map[base] for base in bases])
        time += time_step

        # 건설 잔여 시간 갱신
        for base in bases:
            operating_map[base] -= time_step
            # 잔여 시간이 0일 경우 done에 추가
            if operating_map[base] == 0:
                done.add(base)

    results.append(time)

for result in results:
    sys.stdout.write(str(result)+'\n')

* 설명이 부실할 수 있습니다! 잘못된 부분에 대한 지적과 조언 모두 환영합니다.