[백준 9470] Strahler 순서

https://www.acmicpc.net/problem/9470 문제이해 유향 그래프에서 in-degree가 0인 노드의 순서가 1이라고 하고 나머지 노드의 순서를 문제에 주어진 조건으로 나타낼 때 바다와 만나는 노드의 순서를 구하라. 풀이 처음에는 조건에 맞춰서 DFS로 풀려고 했으나 예외 처리가 힘들어 결국 구글링을 했다.

위상 정렬로 풀어야 하는 것을 알게 되었고 위상 정렬을 공부한 지 오래되어서 아마 안 봤다면 못 풀었을 것 같다. 먼저 indegree = [[0,0,0] for _ in range(M+1)]의 리스트를 만들어 [indegree, 순서, 해당 순서로 들어온 노드의 개수]를 활용해 문제의 조건을 만족하면서 문제를 풀 수 있었다.

코드 import sys from collections import deque, defaultdict T = int(sys.stdin.readline()) for _ in range(T): K, M, P = map(int, sys.st...