[백준/C++] 9470 Strahler 순서

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

9470번: Strahler 순서

코드

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
	int t, k, m, p;
	cin >> t;
	for (int i = 0, result; i < t; i++)
	{
		result = 0;
		cin >> k >> m >> p;
		vector<vector<int>> v(m + 1);
		vector<int> cnt(m + 1);
		vector<int> order(m + 1, 1);
		queue<int> q;
		for (int j = 0, a, b; j < p; j++)
		{
			cin >> a >> b;
			v[a].push_back(b);
			cnt[b]++;
		}

		for (int j = 1; j < m + 1; j++) {
			if (cnt[j] == 0) {
				q.push(j);
			}
		}
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			for (int j = 0; j < v[now].size(); j++) {
				int next = v[now][j];

				if (cnt[next] == 1) order[next] = max(order[now], order[next]);
				else order[next] = max(order[now] + 1, order[next]);

				result = max(order[next], result);
				cnt[next]--;
				if (cnt[next] == 0) q.push(next);
			}
		}
		cout << k << " " << result << "\n";
	}
	return 0;
}

설명

필요한 변수들을 선언해준 후 테스트 케이스 개수를 입력받고 개수만큼 반복문을 돈다. 반복문 내부에서는 기본적으로 위상정렬을 수행한다.  (위상정렬의 정의와 기본 구현은 링크를 참조하시기 바랍니다!)  주어진 하천계의 Strahler 순서를 저장할 변수 result를 0으로 초기화한 후 테스트 케이스 번호 k. 노드의 개수 m, 간선의 개수 p를 입력받는다. 이후 위상정렬에 필요한 벡터들을 선언 및 초기화한다. v는 노드 간 정보를 저장하는 벡터로 v[a]의 원소 b는 a에서 b로 물이 흐른다는 뜻이다. cnt는 진입간선의 개수를 저장하고, order는 각 강의 Strahler 순서를 저장하는 벡터이다.
 
이후 p번 반복문을 돌면서 간선의 정보 a, b를 입력받는다. a에서 b로 물이 흐른다고 했으므로 편의상 보면 a -> b이다. 따라서 a에서 진출하는 노드의 번호를 벡터에 추가해주고,  b의 진입간선을 증가시켜준다. 이후 다시 노드의 개수만큼 반복문을 돌면서 진입차수가 0인, 즉 강의 근원인 노드 번호를 큐에 넣어준다.
 
이제 큐가 빌 때까지 반복문을 돌면서 위상정렬을 수행한다. 현재 큐의 앞에 있는 노드를 뽑아와서 해당 노드에서 나가는 노드들에 대해 반복문을 수행한다. next에 해당 노드에서 나가는 노드 번호를 저장해준다. 이후 나오는 조건문이 강의 순서를 구하는 부분으로 해당 문제에서 제일 중요한 부분이자 기본 위상정렬과의 차이점이다!  cnt[next] == 1이라는 것은 강의 근원은 아니지만(근원일 경우 q.pop에서 제거되었을 것이다.)  하나의 강에서만 뻗어나온 것이므로 " Strahler 순서가 i인 강이 1개이면 순서는 i"을 수행해주면 된다. 이때 " 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i"로 하기 때문에 max(order[now], order[next])로 더 큰 값을 넣어주면 된다. 그리고 else문에서는 "Strahler 순서가 i인 강이2개 이상이면 순서는 i+1"이므로 max(order[now] + 1, order[next])로 더 큰 값을 넣어주면 된다. 그리고 매번 강의 순서를 변경할 때마다 result 값을 강의 순서의 최댓값이 되도록 업데이트해준다. 이후 진입 차수의 개수를 하나 줄이고 cnt[next]가 0이면 큐에 넣어주면 된다. 
 
위상정렬이 끝나면 테스트 케이스 번호 k와 result를 출력해주고 줄바꿈해주면 된다.

느낀 점

기본적인 위상정렬을 수행하면서 강의 순서들을 계속 업데이트하면 되는 문제다.처음에 강에 순서를 붙이는 방법을 잘못 이해해서 예제의 결과가 다르게 나왔는데, 제대로 이해한 후 수정해주었다. 해당 부분만 변경하고 예제가 되는 걸 보고  바로 코드를 제출했는데 통과했다.