728x90
https://www.acmicpc.net/problem/1005
간단한 위상정렬 문제이다.
내가 간단하다고 말하는 기준은 좀 어이없을 수 있지만, 내가 푼 풀이법 그러니까 내 코드가 구글링했을 때 수두룩하게 나오는 다른 사람의 코드와 거의 동일하면 간단한 문제라고 생각한다 ㅋㅋ
풀이법은 다음과 같다.
1. 위상 정렬의 첫 시작은 아무것도 건들지 않은 상태에서 진입차수가 0인 것부터 시작해주면 된다.
2. 하나씩 탐색하면서 해당 노드까지 가는 최장거리를 갱신한다. 이 때 해당 노드의 진입차수가 아직 남아있더라도 max 연산을 통해 모든 경우에서 최댓값을 구해준다.
3. 이 과정에서 진입차수가 0이 된다면 큐에 넣어서 다음 탐색을 위한 발판으로 한다.
import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def topology_sort():
ans = [0] * (n+1)
dq = deque()
# 진입차수가 0인것부터 시작
for i in range(1,n+1):
if indegree[i] == 0:
dq.append(i)
ans[i] = time[i]
while dq:
start = dq.popleft()
for next in construction[start]:
ans[next] = max(time[next] + ans[start],ans[next])
indegree[next] -= 1
if indegree[next] ==0:
dq.append(next)
return ans[w]
if __name__ == "__main__":
t = int(input())
for _ in range(t):
n,k = map(int,input().split())
construction = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
time = [0] + list(map(int,input().split()))
for _ in range(k):
x, y = map(int,input().split())
construction[x].append(y)
indegree[y] += 1
w = int(input())
print(topology_sort())
728x90