코딩하는 사람 울리는 문제 'ACM Craft'
(사나이 울리는 신라면)

처음에 풀었던 당시에는 꽤나 어렵고 힘들었던 문제였는데
갑자기 생각나서 이번엔 이 문제 풀이를 써보겠다.

BOJ 1005 - ACM Craft 링크
(2022.09.08 기준 G3)
(치팅하면 울릴거임)

문제

각 건물마다의 건설 시간과 건물 건설 순서가 주어질 때,
건물 W의 완성 시간

알고리즘

두 정점 간 순서가 정해져 있고 문제에서 모든 정점이 순서대로 방문 가능하다고 적혀 있으므로 (DAG, 비순환 방향 그래프) 위상 정렬을 사용하면 된다.

풀이

백준을 처음 접하여 문제 순서대로 풀게 되면 가장 처음 만나는 어려운 문제. 많은 사람들을 울리고 화나게 만들었을 문제다.

사실 위상 정렬이라는 알고리즘을 정확하게 몰라도 대충 감으로 코드 짜서 해도 풀리긴 한다만, 위상 정렬 태그를 단 이상 위상 정렬 정석대로 코드 풀이를 해보겠다.

먼저 건물 순서를 입력받아 그래프를 완성한다. 이 때, 순서의 후순 건물은 진입차수도 증가시켜야 한다.

그리고 진입차수가 0인 건물들은 바로 건설 시작이 가능한 건물이므로 덱에 넣어준다.

queue = deque() # 덱
for i in range(1, N + 1):
    if not ind[i]: # 진입차수가 0일 경우
        queue.append(i) # 덱에 건물 번호 삽입

그리고 건물 총 완성 시간을 담아줄 배열을 건물 개수만큼 만들어 준다.

X -> Z, Y -> Z 라는 방향 그래프가 있으면 Z는 X와 Y가 완성되어야만 건설 시작이 가능한데, X와 Y가 동시에 건설될 수 있으므로 X와 Y의 완성 시간의 최댓값을 Z의 완성 시간에 넣어주면 된다.
그러면 나중에 Z가 뽑혔을 때, Z의 건설 시간을 더해주면 Z의 총 완성 시간이 구해지는 것이다.

위와 같은 방식을 사용해야 한다.
덱에 들어 있는 건물들을 차례대로 살펴보면서, 그 건물의 완성 시간에 건물 건설 시간을 더해주자. 그리고 그 건물과 연결되어 있는 건물들의 완성 시간과 비교하여 최댓값을 넣어주자.
그리고 진입차수를 감소시키고 만약에 진입차수가 0이 되었다면 그 건물로 진입하는 건물들의 탐색이 끝났다는 말이므로 덱에 삽입하자. 이 과정을 반복하면 된다.
그리고 마지막에 입력받은 W의 건물 완성 시간을 출력하면 끝!

코드

import sys; input = sys.stdin.readline
from collections import deque

def solve():
    N, K = map(int, input().split())
    D = [0] + list(map(int, input().split())) # 건물 번호는 1번부터 시작하므로 앞에 0을 추가
    graph = [[] for _ in range(N + 1)]
    ind = [0] * (N + 1) # 진입차수

    # 건물순서를 입력받아 그래프 완성
    # 후순 건물은 진입차수도 증가시킴
    for _ in range(K):
        X, Y = map(int, input().split())
        graph[X].append(Y)
        ind[Y] += 1

    # 진입차수가 0인 건물들을 모두 찾아서 덱에 넣는다.
    queue = deque()
    for i in range(1, N + 1):
        if not ind[i]:
            queue.append(i)

    build = [0] * (N + 1) # 건물 총 완성 시간
    while queue:
        here = queue.popleft()
        build[here] += D[here] # 건물 건설에 걸리는 시간을 완성 시간에 더해준다.
        for there in graph[here]:
            build[there] = max(build[there], build[here]) # there로 진입하는 건물들의 완성 시간의 최댓값을 there 완성 시간에 넣어준다.
            ind[there] -= 1 # 진입차수 감소
            if not ind[there]: # there의 진입차수가 0이 되면
                queue.append(there) # 덱에 삽입
    print(build[int(input())])

for _ in range(int(input())):
    solve()

여담

위상 정렬을 제대로 익힌 뒤에 풀어보니깐 정말 쉬운 문제가 되었다.
엣날엔 이 문제에 왜 그렇게 쩔쩔맸을까 싶네..? 허허