https://www.acmicpc.net/problem/2056

작업 우선순위가 주어질 때 가장 짧게 작업하는 경우를 구하는 것이다. 위상정렬을 사용해야 한다고 적혀있었다.

Python

1차 시도 - 실패

from collections import defaultdict

n = int(input())

work = list(list(map(int, input().split())) for _ in range(n))

time = dict()

graph = defaultdict(list)
pre = defaultdict(list)

queue = []

for idx, w in enumerate(work):
    graph[idx+1] = []
    time[idx+1] = w[0]

    if w[1] == 0:
        queue.append(idx+1)

    for i in range(w[1]):
        graph[w[i+2]].append(idx+1)
        pre[idx+1].append(w[i+2])

done = [0] * (n+1)

idx = len(queue) - 1

for q in queue:
    done[q] = time[q]

visited = [True] * (n+1)
while idx < len(queue):
    now = queue[idx]
    idx += 1
    visited[now] = False


    for next in graph[now]:
        if visited[next]:
            queue.append(next)
            visited[next] = False


for q in queue:
    if done[q]:
        continue
    t = time[q]
    for next in pre[q]:
        t = max(t, time[q] + done[next])
    done[q] = t


print(done[-1])

graph, pre 등 딕셔너리를 생성하고 BFS로 위상정렬을 했다.(고 생각했다)
그리고 위상정렬한 것을 돌면서 pre에서 우선순위 작업을 찾아서 최대시간을 찾아냈고 맨 마지막 작업이 끝나는 시간을 출력했다. 그리고 실패했다.

BFS를 통해서 위상정렬이 된 줄 알았다. 그러나 코드를 살펴보니 예를 들어 3번 작업을 위해서 1, 2가 끝나야하는 상황일 때 위 코드에서는 1번 작업이 시작되면 3번 작업을 queue에 추가했다.

만약
1 0
2 1 1
3 1 2
4 2 1 3
일 경우에 위 코드에서는 [1, 2, 4, 3]의 순서대로 queue에 들어가게 된다.

from collections import defaultdict

n = int(input())

work = list(list(map(int, input().split())) for _ in range(n))
time = [0] * (n+1)
graph = defaultdict(list)
queue = []
visited = [0] * (n+1)
done = [0] * (n+1)

for idx, w in enumerate(work):
    graph[idx+1] = []
    time[idx+1] = w[0]

    if w[1] == 0:
        queue.append(idx+1)
    else:
        visited[idx+1] = w[1]

    for i in range(w[1]):
        graph[w[i+2]].append(idx+1)


idx = 0

for q in queue:
    done[q] = time[q]

while idx < len(queue):
    now = queue[idx]
    idx += 1

    for next in graph[now]:
        visited[next]-=1
        done[next] = max(done[next], done[now] + time[next])
        if visited[next] == 0:
            queue.append(next)

print(max(done))

visited에 선행하는 작업의 개수를 저장하고, bfs에서 탐새될 때마다 1씩 빼서 queue에 추가되도록 했더니 통과할 수 있었다.

그리고 queue에서 idx를 초기화할 때 len(queue)-1로 했었는데, 0번부터 탐색해야하는데 맨 끝에서부터 탐색하니 계속 실패했던 것 같다.