[BOJ] 위상 정렬 🥇3

📚 Topological Sort

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

💡 풀이

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    k, m, p = map(int, input().split())                 # 테스트 케이스 번호, 노드 개수, 간선 수

    graph = [[] for _ in range(m + 1)]
    inDegree = [0] * (m + 1)                            # 진입차수
    dp = [[0] * (m + 1) for _ in range(m + 1)]
    end = 0                                             # 마지막 노드 번호

    for _ in range(p):                                  # 그래프와 진입 차수 설정
        a, b = map(int, input().split())
        graph[a].append(b)
        inDegree[b] += 1

    queue = deque()
    for i in range(1, m + 1):                           # 진입 차수가 0인 노드를 queue에 추가
        if inDegree[i] == 0:
            queue.append(i)
            dp[i][i] = 1

    while queue:
        x = queue.popleft()
        end = x

        for i in graph[x]:
            inDegree[i] -= 1

            dp[x][i] = dp[x][x]

            if inDegree[i] == 0:
                queue.append(i)
                
                max_ = 0
                count = 0
                for row in range(1, m + 1):
                    if max_ != 0 and dp[row][i] == max_:    # 가장 큰 강의 개수 카운팅
                        count += 1
                    elif dp[row][i] > max_:                 # 가장 큰 강의 개수 찾기
                        max_ = dp[row][i]
                        count = 1

                dp[i][i] = max_ if count == 1 else max_ + 1

    print(k, dp[end][end])
print(*result)

📝 해설

1. 아래와 같은 2차원 리스트(이하 dp)가 있다고 가정한다.

2. 진입 차수가 0인 노드의 번호를 i라고 가정하면, dp[i][i]에 1로 설정한다.

3. 노드 a에서 노드 b로 가는 경로가 있다면, 진입 차수를 감소시키고 dp[a][b]의 값을 dp[a][a] 값으로 변환한다.

4. 진입 차수가 0이 되었다면, queue에 노드 번호를 넣고, 아래의 조건에 따라 dp 테이블의 값을 갱신한다.

• 노드 번호 v에서 해당 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 하였을 때
• 해당 노드로 들어오는 모든 강 중에서 강의 순서가 i인 강이 1개이면, dp[v][v]의 값을 i로 설정한다.
• i인 강이 2개 이상이면 dp[v][v]의 값을 i + 1로 설정한다.

5. 과정 3 ~ 4를 반복하면 아래와 같은 dp 테이블이 만들어진다.

6. 마지막 노드를 v라고 한다면, 하천계의 Strahler 순서는 dp[v][v]가 된다.

💣 고려하지 않아도 되는 사항

dp[x][i] = dp[x][x]

• queue.popleft()를 통해 나온 노드 번호가 v라고 했을 때, dp[v][v] 값은 항상 존재한다.

dp[i][i] = max_ if count == 1 else max_ + 1

• 시작 지점이 아닌 모든 노드에는 진입 간선이 존재하므로 변수 max_는 최소 1의 값을 가지게 된다.
• dp[i][i]는 시작 지점이 아니기 때문에, 가장 큰 강의 개수 i가 1개인지, 2개 이상인지만을 고려하면 된다.