[BOJ/백준] 9470 Strahler 순서

import sys
from collections import deque,defaultdict
input = sys.stdin.readline
# 강의 근원 노드의 순서는 1이다.

T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    # K case의 번호
    # M은 노드의 수
    # P는 간선의 수

    strahelr_dict = [defaultdict(int) for _ in range(M+1)]
    strahelr_list = [-1 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]
    indegree_list = [0 for _ in range(M+1)]
    for _ in range(P):
        x,y = map(int,input().split())
        graph[x].append(y)
        indegree_list[y] += 1
    stack = deque()
    for i in range(1,M+1):
        if not indegree_list[i]:
            stack.append(i)
            strahelr_list[i] = 1
    
    while stack:

        node = stack.popleft()
        cur_strahler = strahelr_list[node]
        for next_node in graph[node]:
            indegree_list[next_node] -= 1
            strahelr_dict[next_node][cur_strahler] += 1
            if not indegree_list[next_node]:
                stack.append(next_node)
                next_strahelr = max(strahelr_dict[next_node].keys())
                if strahelr_dict[next_node][next_strahelr] > 1:
                    strahelr_list[next_node] = next_strahelr + 1
                else:
                    strahelr_list[next_node] = next_strahelr



    print(K,strahelr_list[M])

 이 문제에서 주의해야할 점은,  마지막에 출력해야할 TEST CASE의 값이 T가 아니라, K인걸 주의해야한다.

 

처음은 위상정렬을 해주는 것과 동일하게 indegree와 graph를 그려준다.

 

가장 처음에 출발하는 node들의 strahler의 값을 1로 초기화를 해준다.

 

위상정렬을 해주면서, 방문하는 노드들에 해당 cur_strahler의 개수를 세줍니다.

 

그러면서 indegree가 0이 되었을때, 최대값을 찾고, 그 개수가 2개 이상이면, 최대값보다 1을 더해서 저장시켜줬습니다.

 

위와 같이 한뒤에 나머지는 일반적인 위상정렬을 구하면 되는 문제였습니다.

 

 

# 42_jakang님 풀이
import sys
input = sys.stdin.readline


def tree_dp(cur_node):

    if not len(graph[cur_node]):
        strahler_list[cur_node] = 1
        return
    else:
        max_st_cnt = 0
        for parent_node in graph[cur_node]:
            tree_dp(parent_node)

            if strahler_list[cur_node] < strahler_list[parent_node]:
                strahler_list[cur_node] = strahler_list[parent_node]
                max_st_cnt = 1
            elif strahler_list[cur_node] == strahler_list[parent_node]:
                max_st_cnt += 1
        if max_st_cnt > 1:
            strahler_list[cur_node] += 1
T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    strahler_list = [0 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]

    for _ in range(P):
        x,y = map(int,input().split())
        graph[y].append(x)

    

    tree_dp(M)
    print(K,strahler_list[M])
    

 이 풀이는 42_jakang님의 풀이를 공부하면서 한것이었고, 이 풀이 방식은 다음과 같습니다.

 

어차피 가장 끝노드 M은 고정되어있으므로, 가장 끝 노드에서부터 하나하나씩 부모를 찾아 들어가봅니다.

 

그리고 부모노드의 strahler_list가 현재노드보다 크면 갱신을 해주고, 그 큰값들의 개수를 세줍니다.

 

만약에 그 개수가 2개 이상이면, 현재노드의 shrahler의 값을 키워줍니다.

 

이런 방식을 이용해서도 문제를 풀 수 있습니다.