취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 9470번 문제인 Strahler 순서이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어지는 하천계를 나타내는 그래프는 DAG라 가정하고 풀자.

"강이 시작하는 곳"서부터 시작하여, 각 강의 지점마다 이 지점으로 도달할 수 있는 모든 강을 조사했을 때 다음 탐색 후보로 넣는 것을 반복하면 강이 바다와 만나는 지점(M번 노드)에서의 Strahler Order을 구할 수 있다.

Strahler Order은 이 지점에 합쳐지는 최대 order를 갖는 강이 둘 이상일 때 1이 증가하고, 그렇지 않은 경우 이 지점에 합쳐진 최대 order로 유지된다는 점을 이용하여 각 지점에 합쳐진 강들의 가장 큰 두개의 Strahler Order만을 관리하는 것으로 문제를 해결할 수 있다.

위의 구현은 이 그래프가 DAG라는 것을 가정했으므로 위상정렬(Topological Sort)을 이용하여 해결할 수 있다.

아래는 제출한 소스코드이다.

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

vector<int> G[2001];
int indegree[2001];
int mx[2001][2];
queue<int> que;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		memset(indegree, 0, sizeof(indegree));
		memset(mx, 0, sizeof(mx));
		int K, M, P; cin >> K >> M >> P;
		for (int i = 1; i <= M; i++) G[i].clear();
		while (P--) {
			int A, B; cin >> A >> B;
			G[A].emplace_back(B);
			indegree[B]++;
		}
		for (int i = 1; i <= M; i++) {
			if (!indegree[i]) que.push(i);
		}

		while (!que.empty()) {
			int current = que.front(); que.pop();
			int strahler = (mx[current][0] == mx[current][1]) ? (mx[current][0] + 1) : (mx[current][0]);
			for (auto node : G[current]) {
				if (mx[node][0] < strahler) {
					mx[node][1] = mx[node][0];
					mx[node][0] = strahler;
				}
				else if (mx[node][1] < strahler) mx[node][1] = strahler;
				indegree[node]--;
				if (indegree[node] == 0) que.push(node);
			}
		}

		cout << K << ' ' << ((mx[M][0] == mx[M][1]) ? (mx[M][0] + 1) : (mx[M][0])) << '\n';
	}
}