BOJ 9470 Strahler 순서 - Python

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

잘 이해가 안 됐었던 문제이다.

위상정렬을 응용하면 된다.
Strahler 순서를 구하는 문제인데, 처음 시작하는 곳은 순서가 1이다. 그리고 이에 연결된 노드들은 그 노드로 들어오는 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서가 i + 1 이 된다.

그러니깐 노드의 순서는 들어오는 순서 중 가장 큰 값으로 되는데, 가장 큰 값이 2개 이상이면 가장 큰 값 + 1 이 되는 것이다.

그래서 코드로 구현하면 다음과 같다.

from collections import deque

T = int(input())

while T:
    K, M, P = map(int, input().split())
    arr = [[] for _ in range(M + 1)]
    indegree = [0] * (M + 1)
    count = [[0, 0]] * (M + 1) # [값, 개수]의 배열
    order = [0] * (M + 1)
    queue = deque()

    for i in range(P):
        first, second = map(int, input().split())
        arr[first].append(second)
        indegree[second] += 1

    for i in range(1, M + 1):
        if indegree[i] == 0:
            count[i] = [1, 1]
            queue.append(i)

    while queue:
        temp = queue.popleft()

        if count[temp][1] >= 2: # 개수를 비교해서 값을 갱신한다.
            order[temp] = count[temp][0] + 1
        else:
            order[temp] = count[temp][0]

        for second in arr[temp]:
            indegree[second] -= 1
            if count[second][0] == order[temp]: # 같으면 개수를 증가 시켜준다.
                count[second][1] += 1
            elif count[second][0] < order[temp]: # 이번에 들어오는 값이 더 크다면 바꿔준다.
                count[second] = [order[temp], 1]

            if indegree[second] == 0: # 0 이 됐을 때가 모든 값들을 다 처리 했을 때니깐, 큐에 넣어서 order 값을 갱신 할 수 있도록 한다.
                queue.append(second)

    print(K, end = " ")
    print(order[M])
    T -= 1