[Gold III]
https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
[위상 정렬(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)