[C++] 백준 9470 Strahler 순서

문제 링크

---

www.acmicpc.net/problem/9470

9470번: Strahler 순서

접근 방법

---

 최근 위상 정렬 문제들을 많이 풀면서 대부분 동적계획법의 접근 방법으로 해결이 되어 동적 계획법으로 해결하였다. 

위상을 나타내는 그래프는 vector<int> topology[size]로 나타내었으며, topology[to].push_back(from)으로 입력받아 현제 노드가 어디로부터 왔는지의 정보로 기록하였다.

 

int solve(int now) {

	int &ref = dp[now];
	int number = 0;
	int cnt = 0;

	if (ref != 0) 
		return ref;
	if (topology[now].size() == 0)
		return ref = 1;

	for (int i = 0; i < topology[now].size(); i++) {
		int from = topology[now][i];
		int ret = solve(from);
		if (number < ret) {
			cnt = 1;
			number = ret;
		}
		else if (number == ret) 
			cnt++;
	}

	if (cnt >= 2)
		number += 1;
	return ref = number;
}

 

number로 가장 큰 Strahler순서를 찾았으며, 가장 큰 Strahler순서가 유입된 횟수를 cnt로 카운트하였다.   

 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;

vector<int> topology[1001];
int dp[1001];
int t, k, m, p;

void init() {
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i <= m; i++) 
		topology[i].clear();
}

int solve(int now) {

	int &ref = dp[now];
	int number = 0;
	int cnt = 0;

	if (ref != 0) 
		return ref;
	if (topology[now].size() == 0)
		return ref = 1;

	for (int i = 0; i < topology[now].size(); i++) {
		int from = topology[now][i];
		int ret = solve(from);
		if (number < ret) {
			cnt = 1;
			number = ret;
		}
		else if (number == ret) 
			cnt++;
	}

	if (cnt >= 2)
		number += 1;
	return ref = number;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (--t >= 0) {
		cin >> k >> m >> p;
		init();
		for (int i = 0; i < p; i++) {
			int from, to;
			cin >> from >> to;
			topology[to].push_back(from);
		}
		cout << k << " " << solve(m) << "\n";
	}
}

개발 환경 : VS2017

질문, 지적 환영합니다!