백준1516 - 게임 개발

전략

1. 위상 정렬을 이용

2. 현재 비용과 나중에 계산된 비용을 비교해서 더 큰 비용을 가져간다.

코드

from sys import stdin, stdout

def topology(timeCost, delayTime, a, N, d):
  q = []
  for i in range(1, N + 1):
    if d[i] == 0:
      q.append(i)
  for i in range(1, N + 1):
    x = q.pop(0)
    for j in range(0, len(a[x])):
      y = a[x][j]
      d[y] -= 1
      delayTime[y] = max(delayTime[y], timeCost[y] + delayTime[x])
      if d[y] == 0:
        q.append(y)
  return delayTime

N = int(stdin.readline())
timeCost = [0 for _ in range(N + 1)]
delayTime = [0 for _ in range(N + 1)]
a = [[] for _ in range(N + 1)]
d = [0 for _ in range(N + 1)]

for i in range(N):
  row = list(map(int, stdin.readline().split(' ')))
  timeCost[i + 1] = row.pop(0)
  delayTime[i + 1] = timeCost[i + 1]
  row.pop()
  d[i + 1] = len(row)
  for item in row:
    a[item].append(i + 1)

delayTime = topology(timeCost, delayTime, a, N, d)

for i in range(1, N + 1):
  stdout.write(str(delayTime[i]) + '\\n')