BOJ : 9470 Strahler 순서

---

[BOJ 9470(G3)리뷰]

처음에 문제 설명만 읽고는 문제를 이해하기 힘들었다. 결국은 위상정렬 문제인데 특별한 조건이 추가된 위상정렬이라고 생각하면 된다.

강이 시작하는 노드(들어오는 간선이 없는 경우)의 순서는 1번부터 시작한다. 입력은 "1 3"이런식으로 주어지는데 1번강에서 3번강으로 물이 흘러나간다는 소리이다. 이 때 들어오는 간선이 존재하는(3번노드) 노드의 정보는 자신에게 들어오는 노드 중 가장 큰 값의 크기에 따라 결정된다. 가장 큰 값이 2개 이상일 경우 이전 강의 값에 +1, 2개 미만일 경우는 이전 강의 정보를 그대로 가진다.

위 조건을 만족하기 위하여 별도의 배열을 만들었다. 해당 번호에 들어오는 물 중 가장 큰 값과, 그 갯수를 저장하는 코드를 추가했다.

나머지는 위상정렬 알고리즘과 똑같이 해주며 들어오는 값의 크기가 2이상일경우 이전값에 +1만 해주면 된다.

/*
	21.01.22
	BOJ : 9470 Strahler 순서 (https://www.acmicpc.net/problem/9470)
	위상정렬
*/
#include <bits/stdc++.h>
using namespace std;

int tc;
int k, m, p;
vector <int> adj[1001];
int indegree[1001];
int strahler[1001];
pair<int, int> info[1001];
queue <int> q;

void init() {
	for (int i = 1; i <= m; i++) {
		adj[i].clear();
	}

	memset(indegree, 0x00, sizeof(indegree));
	memset(strahler, 0x00, sizeof(strahler));
	memset(info, 0x00, sizeof(info));
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> tc;

	while(tc--) {
		cin >> k >> m >> p;
		int ans = 0;
		for (int i = 0; i < p; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			indegree[b]++;
		}

		
		for (int i = 1; i <= m; i++) {
			if (indegree[i] == 0) {
				q.push(i);
			}
		}

		while (!q.empty()) {
			int cur = q.front(); q.pop();A
			int n = info[cur].first;
			int c = info[cur].second;

			if (c == 1) {
				strahler[cur] = n;
			}
			else {
				strahler[cur] = n + 1;
			}

			ans = max(ans, strahler[cur]);
			for (int i = 0; i < adj[cur].size(); i++) {
				int nxt = adj[cur][i];

				indegree[nxt]--;
				if (indegree[nxt] == 0) {
					q.push(nxt);
				}

				if (info[nxt].first < strahler[cur]) {
					info[nxt].first = strahler[cur];
					info[nxt].second = 1;
				}
				else if (info[nxt].first == strahler[cur]) {
					info[nxt].second += 1;
				}
			}
		}

		cout << k << " " << ans << '\n';
		init();
	}

	return 0;
}