[파이썬/python] 백준 - 9470 Strahler 순서

문제

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

---

문제 설명

1. 하천계는 유향그래프로 나타낼 수 있다.
   1. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다.
   2. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳, 바다와 만나는 곳
2. 네모 안의 숫자는 Strahler 순서를 나타내고 동그라미 안의 숫자는 노드 번호를 나타낸다.
   1. 강의 근원인 노드의 순서는 1이다.
   2. 나머지 노드는 그 노드로 들어오는 강의 Strahler 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강의 1개면 순서는 i, 2개 이상이면 순서는 i+1이다.
3. 하천계의 순서는 바다와 만나는 노드의 순서와 같다. 바다와 만나는 노드(K번이 항상 바다와 만나는 노드이다.)는 항상 1개이며 아래 그림에서 Strahler 순서는 3이다.
4. 하천계 정보가 주어졌을 때 Strahler 순서를 구한다.

문제 그림

---

풀이

문제를 이해하는 시간이 정말 오래 걸렸던 것 같다.

 

먼저 Strahler 순서가 무언인지부터 되짚어보자.

1. 강의 근원인 노드의 순서는 1이다.
2. 나머지 노드는 그 노드로 들어오는 강의 Strahler 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강의 1개면 순서는 i, 2개 이상이면 순서는 i+1이다.

1번 조건은 강의 근원, 즉 강이 시작되는 지점을 의미한다. 문제의 그림에서는 1번, 2번, 6번이 이와 같다.

2번 조건은 4번, 5번, 7번 노드를 통해 확인해 보자.

 

4번 노드로 들어오는 강의 Strahler 순서는 3번 노드(2), 6번 노드(1)이다.

따라서 4번 노드의 Strahler 순서는 가장 큰 2가 된다.

 

이때 착각하면 안 되는 조건이 하나 존재한다.(나는 처음에 착각했다.)

2번 조건에서

2개 이상이면 순서는 i+1이다.라는 말은 가장 큰 i가 2개 이상이어야 한다는 말이다.

만약 들어오는 강의 Strahler 순서가 [1,2,3]이라면 가장 큰 i인 3이 1개밖에 존재하지 않기 때문에 그 노드의 Strahler 순서는 i+1이 아니라 i인 3이 된다는 것이다.

 

그럼 다음 노드를 마저 확인해 보자.

 

5번 노드로 들어오는 강의 Strahler 순서는 3번 노드(2)밖에 존재하지 않는다.

따라서 5번 노드의 Strahler 순서는 2가 된다.

 

7번 노드로 들어오는 강의 Strahler 순서는 4번 노드(2), 5번 노드(2), 6번 노드(1) 세 개가 존재한다.

따라서 7번 노드의 Strahler 순서는 가장 큰 i인 2가 1개 이상 존재하기 때문에 i+1 = 3이 된다.

 

세 노드의  Strahler 순서가 어떻게 정해지는지 이해했다면 이제 코드를 작성할 수 있다.

 

알고리즘은 위상정렬을 사용했다. 현재 강으로 들어오는 강들의  Strahler 순서를 전부 알아야 현재 강의  Strahler 순서를 구할 수 있기 때문에 강들의 순서를 통해 탐색을 해야 하기 때문이다.

 

이후부터는 위상정렬의 기본 틀과 똑같다. 차수를 구한 후 Queue를 통해 진입 차수가 0인 노드부터 차례대로 꺼내면서 Strahler 순서를 갱신하면 된다.

이때 Strahler 순서를 저장하고 꺼낼 때는 heap 구조를 사용해서 최댓값을 꺼내도록 구현했다.

 

기존 위상정렬보다 약간 꼬아서 난도가 높은 것 같지만, 위상정렬에 대해 잘 이해하고 있다면 어렵지 않게 풀 수 있는 문제였다.

 

 

 

---

코드

import sys
from collections import deque
import heapq
input = sys.stdin.readline


for tc in range(1, int(input()) + 1):


    k,m,p = map(int,input().split())

    degree = [0 for _ in range(m+1)]
    graph = [[] for _ in range(m+1)]

    for i in range(p):
        a,b = map(int,input().split())
        degree[b] += 1
        graph[a].append((b))
        graph[b].append((a))


    strahler = [[0,[]] for _ in range(m+1)]
    queue = deque()
    res = [0 for _ in range(m+1)]
    for i in range(1,m+1):
        if degree[i] == 0:
            queue.append(i)
            strahler[i][0] = 1
            heapq.heappush(strahler[i][1], -1)


    
    while queue:
        v1 = queue.popleft()

        strahler[v1][0] = -heapq.heappop(strahler[v1][1])
        if len(strahler[v1][1]) > 0 and strahler[v1][0] == -heapq.heappop(strahler[v1][1]):
            strahler[v1][0] += 1

        for v2 in graph[v1]:

            if degree[v2] > 0:
                heapq.heappush(strahler[v2][1], -strahler[v1][0])
                degree[v2] -= 1

                if degree[v2] == 0:
                    queue.append(v2)
        
    print(k,strahler[m][0])

---

시간복잡도

• 위상정렬의 시간복잡도는 $O(V+E)$이다.
• 최악의 경우 $T = 1000, V = 1000, E = V-1$이다.
• 따라서 약 $O(1000*(1000+1000) = O(2*10^6)$의 시간복잡도가 소요된다.