[백준] 1005. ACM Craft - 파이썬

[Gold III]

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

1005번: ACM Craft

 

[위상 정렬(Topological Sort)] 참고.

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

 

풀이 1

위상 정렬(Topological Sort)을 이용하여 풀이.

오답이 나왔는데, 잘 생각해보니 각 턴마다 건설 시간이 가장 긴 것을 더하는 것이 총 건설 시간의 합이 최소가 되도록 하지 않는다는 것을 깨달았다.

 

from collections import deque
T = int(input())
result = []
 
for _ in range(T):
    N, K = map(int, input().split())
    times = list(map(int, input().split()))
 
    '''그래프 저장'''
    graph_in = dict()
    graph_out = dict()
    for _ in range(K):
        a, b = map(int, input().split())
        '''위상 정렬(Topological Sort)에서는 나가는 간선의 수(진출 차수)와 들어오는 간선의 수(진입 차수)가 모두 필요.'''
        if graph_out.get(a):
            graph_out[a].append(b)
        else:
            graph_out[a] = [b]
 
        if graph_in.get(b):
            graph_in[b] += 1
        else:
            graph_in[b] = 1
 
    '''지어야 하는 건물의 번호 W 저장'''
    W = int(input())
 
    '''진입 차수가 0인 vertex를 queue에 삽입'''
    queue = deque([])
    for i in range(1, N+1):
        if not graph_in.get(i) or graph_in[i] == 0:
            queue.append(i)
 
    queue_copy = queue
    total_time = 0
 
    '''동시 건설이 가능하므로, queue를 두개 이용하는 형식으로 턴을 나눔'''
    while queue_copy:
        queue_copy = deque([])
        turn_time = []
        while queue:
            '''queue에서 vertex pop'''
            a = queue.popleft()
            '''이번 반복(턴)의 시간들 저장'''
            turn_time.append(times[a-1])
            '''queue에서 pop하여 연결된 vertex들의 진입 차수 1씩 감소, 진입 차수가 0이 되었다면 queue에 추가'''
            for t in graph_out.get(a, []):
                graph_in[t] -= 1
                if graph_in[t] == 0:
                    queue_copy.append(t)
 
        '''이번 턴 중 가장 긴 시간이 걸리는 것을 채택'''
        total_time += max(turn_time)
 
        queue = queue_copy
 
        '''만약 다음 턴에 W가 있다면, W만 지으면 끝이므로 현재 total_time에 W 건설시간만 추가'''
        if W in queue:
            total_time += times[W-1]
            break
 
    result.append(total_time)
 
for i in result:
    print(i)

 

풀이 2

각 턴(단계)마다 건설 시간이 가장 긴 것을 더하는 것이 총 건설 시간의 합이 최소가 되도록 하지 않음.

예를 들면, 아래와 같은 input 예시에서는, 풀이 1로는 '32'가 출력되지만, 정답은 '28'.

1
6 6
10 5 1 1 9 8
1 2
1 4
2 3
4 5
3 6
5 6
6

이렇게 착각한 것은, 현재 건설중인 건물이 없어야 건설을 시작할 수 있다고 착각했기 때문.

따라서, 건설 시작은 조건만 맞으면 언제든지 할 수 있으므로, 건설의 각 턴(단계)를 따질 것이 아닌, 각 건물을 지을 수 있는 가장 빠른 시간을 구해야 한다.

위의 input을 예시로 들면, 6을 지어야 하므로, 3과 5의 건설이 각각 완성될 수 있는 최소 시간을 구해야 하고,

3을 지어야 하므로, 2가 완성되는 최소의 시간, 5를 지어야 하므로, 4가 완성되는 최소의 시간...~

이를 구하기 위해서는, DP를 활용하여 건물 N을 짓는 데 걸리는 최소 시간을 dp[N]에 저장하는 식으로.. 구현하면 된다.

 

line 46 ~ line 69의 while문 안쪽을, DP로 교체한 것을 확인할 수 있다.

그 도중 필요했기에 진입하는 간선을 저장하는 dictionary도 새로 선언하여 사용하였다.

성공!

from collections import deque
T = int(input())
result = []
 
for _ in range(T):
    N, K = map(int, input().split())
    times = list(map(int, input().split()))
 
    '''그래프 저장'''
    graph_in_cnt = dict()
    graph_in = dict()
    graph_out = dict()
    for _ in range(K):
        a, b = map(int, input().split())
        '''위상 정렬(Topological Sort)에서는 나가는 간선의 수(진출 차수)와 들어오는 간선의 수(진입 차수)가 모두 필요.'''
        if graph_out.get(a):
            graph_out[a].append(b)
        else:
            graph_out[a] = [b]
 
        if graph_in.get(b):
            graph_in[b].append(a)
        else:
            graph_in[b] = [a]
 
        if graph_in_cnt.get(b):
            graph_in_cnt[b] += 1
        else:
            graph_in_cnt[b] = 1
 
    '''지어야 하는 건물의 번호 W 저장'''
    W = int(input())
 
    '''진입 차수가 0인 vertex를 queue에 삽입'''
    queue = deque([])
    for i in range(1, N+1):
        if not graph_in_cnt.get(i) or graph_in[i] == 0:
            queue.append(i)
 
    queue_copy = queue
    total_time = 0
 
    dp = dict()
 
    '''Bottom-Up 형식의 DP'''
    while queue:
        '''queue에서 vertex pop'''
        a = queue.popleft()
        '''queue에서 pop하여 연결된 vertex들의 진입 차수 1씩 감소, 진입 차수가 0이 되었다면 queue에 추가'''
        for t in graph_out.get(a, []):
            graph_in_cnt[t] -= 1
            if graph_in_cnt[t] == 0:
                queue_copy.append(t)
 
        '''a를 짓는 데 걸리는 최소의 시간.'''
        '''만약 graph_in[a] = [b, c]라면, dp[a] = max(dp[b], dp[c]) + times[a-1]가 될 것이다.'''
        if not graph_in.get(a):
            dp[a] = times[a-1]
        else:
            max_prepare = 0
            for building in graph_in[a]:
                if max_prepare < dp[building]:
                    max_prepare = dp[building]
 
            dp[a] = max_prepare + times[a-1]
 
        if a == W:
            result.append(dp[a])
            break
 
for i in result:
    print(i)