[BOJ] [Python] 1005 : ACM Craft

위상 정렬로 해결했다.

 

 

import sys

input = sys.stdin.readline

T = int(input())  # 테스트케이스의 개수

for _ in range(T):
    N, K = map(int, input().split())  # 건물의 개수, 건설 순서 규칙의 총 개수

    dp = [0] * (N + 1)

    queue = []
    graph = []

    check = [0] * (N + 1)  # 전입 차수
    val = [0]   # 건설 시간

    order = [1] * (N + 1)   # 출력될 수 있는 순서
    result = [0] * (N + 1)  # 건물 시간 결과

    val += list(map(int, input().split()))

    for _ in range(N + 1):
        graph.append([])

    for _ in range(K):
        X, Y = map(int, input().split())

        check[Y] += 1
        graph[X].append(Y)

        dp[Y] = 1

    for i in range(1, N + 1):
        if dp[i] == 0:
            queue.append(i)

            result[i] = val[i]

    while queue:

        num = queue.pop(0)

        if not graph[num]:
            continue

        tmp = order[num]

        for next_num in graph[num]:

            result[next_num] = max(result[next_num], val[next_num] + result[num])

            check[next_num] -= 1

            if check[next_num] == 0:
                order[next_num] = order[num] + 1
                queue.append(next_num)

    # print(result)

    W = int(input())
    print(result[W])

 

 

풀면서 단단히 착각한 부분이 있다.

 

A to B라고 할 때, A의 최소 출력 순서에 따라서 B의 시간이 결정된다고 생각했다.

 

# ex)
# 1 -> 2 -> 4 -> 3
# 1 -> 5 -> 3

 

4의 최소 출력 순서는 3이다.

5의 최소 출력 순서는 2이다.

 

그러면 3은 무조건 4의 시간을 따라간다고 생각했다. 

 

근데 4가 만약 1s가 걸리고 5가 100s가 걸린다면,

5를 따라가야 한다. (2는 신경 쓰지 않는다고 가정.)

 

 

# ex)

# 1: 1s, 2: 2s, 3: 100s, 4: 4s
# 1 -> 2
# 1 -> 3
# 2 -> 4

# 1 -> (2, 3) -> 4
# 4 == 7s

# ex)
# 1: 1s, 2: 2s, 3: 100s, 4: 4s
# 1 -> 2
# 1 -> 3
# 2 -> 4
# 3 -> 4

# 1 -> (2, 3) -> 4
# 4 == 105s

 

그리고 위 예시에서 알 수 있듯이,

무조건 4와 5다음에 3이 큐에 삽입되기 때문에 최소 출력 순서는 신경 쓸 필요가 없다.

 

3의 시간은 4가 가져온 값과 5가 가져온 값 중 더 큰 값이다.

 

 

아래는 착각의 늪에 빠져버린 코드이다. (코드 설명은 생략하겠다.)

 

 

      if same_order_check[next_num] < tmp:
                result[next_num] = val[next_num] + result[num]

                same_order_check[next_num] = tmp

    elif same_order_check[next_num] == tmp:
    result[next_num] = max(result[next_num], val[next_num] + result[num])

 

 

문제를 정확히 이해하지 못해서 일어난 일이다. 착각하는 일 없도록 하자.