ACM Craft

ACM Craft는 전형적인 위상정렬을 사용하는 문제이다.

내 풀이

나는 아래와 같은 해결책을 생각해냈는데 이는 예를 들어서 4번을 가기 위해서 2, 3번이 필요하고 2번을 가기 위해서 1번이 필요할 때, 2번과 3번이 동시에 건설이 진행되기 때문에 둘 중 큰 값이 해당 차수를 진행하는 시간이 된다.

role = []
build_time = []
goal = []
testcase_cnt = 0
def custom_sys.stdin.readline():
  global role, build_time, goal, testcase_cnt
  testcase_cnt = int(sys.stdin.readline())
 
  for _ in range(testcase_cnt):
    _role = {}
    _building_cnt, _older_cnt = map(int, sys.stdin.readline().split())
 
    _build_time = list(map(int, sys.stdin.readline().split()))
 
    for _ in range(_older_cnt):
      a, b = map(int, sys.stdin.readline().split())
      if b in _role :
        _role[b].append(a)
      else:
        _role[b] = [a]
 
    role.append(_role)
    goal.append(int(sys.stdin.readline()))
    build_time.append(_build_time)
 
from collections import deque
 
def bfs(graph, v, build_time):
  ans = 0
  visited = []
  q = deque([v])
 
  while q:
    cur_v = q.popleft()
    ans += build_time[cur_v - 1]
    if cur_v in graph :
      for _v in graph[cur_v]:
        if _v not in visited:
          visited.append(_v)
          q.append(_v)
 
  return ans
 
def main():
  global role, build_time, goal, testcase_cnt
  custom_sys.stdin.readline()
  for case in range(testcase_cnt):
    print(bfs(role[case], goal[case], build_time[case]))
 
main()

내 풀이 2

문제를 복기하다가 이거 다익스트라로 풀 수 있지 않을까? 라는 생각이 들었다.
가능한 최소 비용을 계산하는 문제에 최단 경로 알고리즘을 사용하면 안된다는 것을 배웠다. 여기서 가능한이라는 개념은

import heapq
 
n = int(input())
 
for _ in range(n) :
  v, e = map(int,input().split())
  times = [0] + list(map(int,input().split()))
  indegree = [0 for _ in range(v + 1)]
  rule = {}
  dp = {}
  for i in range(v + 1) :
    rule[i] = []
  for i in range(1, v + 1) :
    a, b = map(int, input().split())
    rule[a].append(b)
    indegree[b] += 1
 
  pq = []
  for i in indegree :
    pq.append([times[i], i])
  heapq.heapify(pq)
 
  while pq :
    cur_cost, cur_v = heapq.heappop(pq)
    if cur_v not in dp :
      dp[cur_v] = cur_cost
      for v in rule[cur_v] :
        cost = times[v]
        if v not in dp :
          heapq.heappush(pq,[cost + cur_cost, v])
  goal = int(input())
  print(dp[goal])

다른 사람 풀이

참조한 블로그 (opens in a new tab)

import sys
from collections import deque
 
T = int(sys.stdin.readline())
 
for _ in range(T):
  N, K = map(int, sys.stdin.readline().split())  # 건물수, 건설순서규칙
  time = [0] + list(map(int, sys.stdin.readline().split()))  # 건물들의 건설시간
  seq = [[] for _ in range(N + 1)]  # 건설순서규칙
  in_degree = [0 for _ in range(N + 1)]  # 진입차수
  DP = [0 for _ in range(N + 1)]  # 해당 건물까지 걸리는 시간
 
  for _ in range(K):  # 건설순서규칙 저장
    a, b = map(int, sys.stdin.readline().split())
    seq[a].append(b)
    in_degree[b] += 1
 
  q = deque()
  # 나를 향하는 간선이 없는거 찾아서 큐에 넣기 
  for i in range(1, N + 1): 
    if in_degree[i] == 0:
      q.append(i)
      DP[i] = time[i]
 
  while q :
    a = q.popleft()
    for i in seq[a]:
      in_degree[i] -= 1  # 나를 향하는 간선 줄이고
      # DP[i]는 현재 노드 DP[a]는 현재 노드로 오기위해서 필요한 이전 노드의 값을 의미한다.
      DP[i] = max(DP[a] + time[i], DP[i])  # DP를 이용해 건설비용 최대값으로 갱신
      # 나를 향하는 간선이 0개가 되면 큐에 넣기 
      if in_degree[i] == 0:
        q.append(i)
 
  ans = int(sys.stdin.readline())
  print(DP[ans])

피보나치 함수 리모컨