접근 위상 정렬을 이용해 현재 접근 가능한 수 중 가장 작은 값을 출력한다 N 사이즈의 풀 수 있는 다음 문제가 담긴 2차원 리스트, 접근하기 위해 풀어야 하는 선행 문제의 갯수가 담긴 int 리스트를 선언한다. M 개의 조건문을 받고 A -> B 를 바라보도록 리스트에 추가해준다. B 의 선행문제 갯수는 하나 올라간다. 선행문제 카운트 리스트를 훑으며 지금 진입 가능한 (선행문제가 0인) 문제 번호들을 Priority Queue 에 넣는다. Priority Queue 에서 값을 뽑는다. 이 문제가 바라보는 다음 문제들을 훝으며 각각의 선행 문제 갯수를 하나씩 뺀다. 이 과정에서 선행 문제 갯수가 0이 된 문제들을 Queue 에 추가해준다. 사고 혹시나 나처럼 헷갈리는 이들이 있을까 싶어 문제 조건을 확실히 해두고 싶다. ...
solved.ac class 5의 essential 문제로, 위상 정렬에 대한 이해가 있다면 어렵지 않게 풀수 있다. 위상 정렬에 대해서는 따로 알고리즘 포스팅에 정리해놓겠다. 문제를 풀때 사고방식은 이랬다. 특정 건물 K를 짓기 시작하는 시점은 이전에 지어야 하는 건물들 중 가장 오래 걸리는 건물들을 선택해서 도달한 시점이다. 여기에서 dp 개념이 필요하며, 나머지는 백준 2252 줄 세우기 문제의 위상 정렬 접근법을 이용한다. import sys from collections import deque input = sys.stdin.readline T = int(input()) for test in range(T): N, K = map(int, input().split()) time = list(map(int, input().split())) cnt_enter_link = [0] * (N) graph = [[] for _ in range(N)] dp_build_time = [0] * (N) for _ in range(K): a, b = map(int, input().split()) graph[a - 1].append(b - 1) cnt_enter_link[b - 1] += 1 q = deque() for i in range(N): if cnt_enter_link[i] == 0: q.append(i) w = int(input()) - 1 while(q): c = q.popleft() if c == w: print(dp_build_time[c] + time[c]) for i in graph[c]: cnt_enter_link[i] -= 1 dp_build_time[i] = max(dp_build_time[i], dp_build_time[c] + time[c]) if cnt_enter_link[i] == 0: q.append(i)