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

문제

 

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

9470번: Strahler 순서

지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳, 바다와 만나는 곳이다.

네모 안의 숫자는 순서를 나타내고, 동그라미 안의 숫자는 노드 번호를 나타낸다.

하천계의 Strahler 순서는 다음과 같이 구할 수 있다.

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

하천계의 순서는 바다와 만나는 노드의 순서와 같다. 바다와 만나는 노드는 항상 1개이며, 위의 그림의 Strahler 순서는 3이다.

하천계의 정보가 주어졌을 때, Strahler 순서를 구하는 프로그램을 작성하시오.

실제 강 중에서 Strahler 순서가 가장 큰 강은 아마존 강(12)이며, 미국에서 가장 큰 값을 갖는 강은 미시시피 강(10)이다.

노드 M은 항상 바다와 만나는 노드이다.

입력

첫째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 1000)가 주어진다.

각 테스트 케이스의 첫째 줄에는 K, M, P가 주어진다. K는 테스트 케이스 번호, M은 노드의 수, P는 간선의 수이다. (2 ≤ M ≤ 1000) 다음 P개 줄에는 간선의 정보를 나타내는 A, B가 주어지며, A에서 B로 물이 흐른다는 뜻이다. (1 ≤ A, B ≤ M) M은 항상 바다와 만나는 노드이며, 밖으로 향하는 간선은 존재하지 않는다.

출력

각 테스트 케이스마다 테스트 케이스 번호와 입력으로 주어진 하천계의 Strahler 순서를 한 줄에 하나씩 출력한다.

 

 

 

---

풀이

 

문제 보면서 서클이 없는 위상정렬과 유사하다는 생각이 들었다.

각 노드의 진입차수를 저장해두고 진입차수가 0인 노드를 방문처리하고 큐에 넣는다.

큐에서 하나씩 pop해서 해당 노드로부터 다른노드 a, b로 간다고 할 때

a와 b의 진입차수를 하나씩 낮춰준다.

우리는 strahler순서도 알아야하기 때문에 같이 계산해준다.

다시 진입차수가 0이 된 노드를 큐에 넣고 위의 과정을 큐가 빌 때까지 반복한다.

위상정렬을 하려면 큐에서 팝한것을 따로 저장해줘야하지만 이 문제에서는 요구하지 않기에 저장하지 않았다.

마지막 strahler순서 배열(astra)의 값 중 가장 큰 값을 출력한다.

 

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

t = int(input())

def strahler():
    k, m, p = map(int, input().split())
    g = [[] for _ in range(m + 1)] #그래프 만들기
    ind = [0] * (m + 1)
    for i in range(p):
        a, b = map(int, input().split())
        g[a].append(b)
        ind[b] += 1 #진입차수 저장

    q = deque([])
    visited = [False] * (m + 1)
    bstra = [[] for _ in range(m + 1)] #노드로 들어오는 강의 순서들
    astra = [0] * (m + 1) #해당 노드의 strahler 순서
    for i in range(1, m + 1):
        if ind[i] == 0 and not visited[i]:
            visited[i] = True
            q.append(i)
            bstra[i].append(1) #진입차수가 0인 노드의 순서 1로 초기화
            astra[i] = 1 #진입차수가 0인 노드의 순서 1로 초기화

	#위상정렬과 유사함
    while q: 
        now = q.popleft()
        for n in g[now]:
            ind[n] -= 1 #진입차수 1 낮춰줌
            bstra[n].append(astra[now])

        for i in range(1, m + 1):
            if ind[i] == 0 and not visited[i]:
                visited[i] = True
                q.append(i)
                # 제일 큰 순서값과 그 값이 2개 이상인지
                maxb = 0
                maxn = 0
                for b in bstra[i]:
                    if maxb < b:
                        maxb = b
                        maxn = 1
                    elif maxb == b:
                        maxn += 1
                if maxn > 1:
                    astra[i] = maxb + 1 #i+1
                else:
                    astra[i] = maxb # i

    print(k, max(astra))
    return

for _ in range(t):
    strahler()

솔직히 바로 될 줄 몰랐는데 한번에 통과했다. (｡･∀･)ﾉﾞ