1005_ACM Craft

입력

첫째 줄에 총 건물 개수(N), 건설 조건 개수(K) 입력
둘째 줄부터 K+1번째 줄까지 건설 조건 입력
K+2번째 줄에 최종으로 건설해야 하는 건물 입력

출력

최종 건물을 건설하기 위한 시간을 출력

조건

• 관계에서 사이클이 존재하지 않음

풀이

1. 건물 시간을 확인하기 위한 리스트(delay), indegree를 확인하기 위한 딕셔너리(indeg), 각 건물마다 최종적으로 걸리는 시간을 확인하기 위한 리스트(ans) 선언

  N, K = map(int, sys.stdin.readline().split())

    delay = list((map(int, sys.stdin.readline().split())))
    indeg = {build:[[],0] for build in range(1, N+1)}

    for _ in range(K):
        a, b = map(int, sys.stdin.readline().split())
        indeg[a][0].append(b)
        indeg[b][1] += 1

    win = int(input())

    q = deque([])
    ans = [delay[idx] for idx in range(N)]

2. indegree가 0인 값들로 큐를 초기 설정

    for build in range(1, N+1):
        if indeg[build][1] == 0: q.append(build)

3. 큐가 empty일 때까지 반복문을 돌며
   현재 고려하는 건물이 최종 건물일 경우 stop
   그렇지 않다면 현재 고려하는 건물을 지은 이후 건설할 수 있는 건물들에 대한 indegree를 -1 감소 후 해당 건물의 indegree가 0이 될 경우 최종 건설 시간을 최대값으로 update하고 큐에 추가

    while q:
        curr = q.popleft()

        if curr == win: break

        for next_ in indeg[curr][0]:
            indeg[next_][1] -= 1
            ans[next_-1] = max(ans[next_-1], delay[next_-1]+ans[curr-1])

            if indeg[next_][1] == 0: q.append(next_)

전체 코드

ACM Craft