[백준 / Python] 게임 개발_1516

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

 

 

 

 

정답 풀이

from _collections import deque
 
n = int(input())
data = [[] for _ in range(n + 1)]
indegree = [0 for _ in range(n + 1)]
time = [0 for _ in range(n + 1)]
 
for i in range(1, n + 1):
    detail_data = list(map(int, input().split()))
    detail_data = detail_data[:len(detail_data) - 1]
    time[i] = detail_data[0]
    for j in range(1, len(detail_data)):
        data[detail_data[j]].append(i)
        indegree[i] += 1
 
 
def topology_sort():
    q = deque()
    dp = [0 for _ in range(n+1)]
    for i in range(1, n+1):
        dp[i] = time[i]
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append((i, 0))
 
    while q:
        new_node, node = q.popleft()
 
        for i in data[new_node]:
            indegree[i] -= 1
            dp[i] = max(dp[new_node] + time[i], dp[i])
 
            if indegree[i] == 0:
                q.append((i, new_node))
 
 
    for i in range(1, n+1):
        print(dp[i])
 
 
topology_sort()
 

 

 

처음 제출했던 틀린 풀이

from _collections import deque
 
n = int(input())
data = [[] for _ in range(n + 1)]
indegree = [0 for _ in range(n + 1)]
time = [0 for _ in range(n + 1)]
 
for i in range(1, n + 1):
    detail_data = list(map(int, input().split()))
    detail_data = detail_data[:len(detail_data) - 1]
    time[i] = detail_data[0]
    for j in range(1, len(detail_data)):
        data[detail_data[j]].append(i)
        indegree[i] += 1
 
 
def topology_sort():
    q = deque()
    dp = [0 for _ in range(n+1)]
    for i in range(1, n+1):
        dp[i] = time[i]
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append((i, 0))
 
    while q:
        new_node, node = q.popleft()
        dp[new_node] = max(dp[new_node], dp[node] + time[new_node])
 
        for i in data[new_node]:
            indegree[i] -= 1
 
            if indegree[i] == 0:
                q.append((i, new_node))
 
 
    for i in range(1, n+1):
        print(dp[i])
 
 
topology_sort()
 

 

 

처음 문제를 접한 방식

우선 문제 해석을 잘해야 했다. 처음 문제를 봤을 때는 간선이 연결되어 있는 노드 중, 가장 적은 시간을 더 하기만 하면 되는 줄 알았다.

하지만 그림과 같은 예시에서 3이 완성 되려면, 총 5시간 값을 가진다.

처음 잘못 이해해서 값이 4이거나 6인 줄 알았다. (두개가 다 완성되어야 하거나, 둘 중 적은 값만 계산하면 되는 줄 알았다.)

문제 예시를 본 후에 둘 중 큰 값을 더해줘야 한다는 걸 알았고, 처음 제출했던 풀이가 나왔다.

 

 

 

처음 풀이가 틀렸던 이유

처음 틀린 풀이는 indegree가 0일 때, 값을 넣어주기 떄문에 new_node가 4이고 node가 5일 때 값을 못 바꿔준다.

그리고 나중에 new_node = 4, node = 3이 되서야 값을 바꿔주는데, 이 값을 5보다 작을 수도 있으므로 오답처리가 된 것이다.

즉, 간선에 연결되어 있는 노드들 중에서 가장 큰 값으로 갱신을 해줘야 하는데 indegree가 0이 됐을 때만 갱신해주니 오답처리가 된 것이다.