백준 9420 - Strahler 순서(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9470

9470번: Strahler 순서

위상 정렬 알고리즘을 이용한 문제입니다.

주어진 강의 Strahler 값을 구하는 문제입니다.

Strahler 순서를 구하는 방법은
1. 강이 시작하는 곳은 순서가 항상 1이다.
2. 강이 만나는 곳은 들어오는 강 중, 가장 큰 Strahler 값을 가져온다.
    2-1. 이때, 가장 큰 Strahler 값이 2개 이상이면 해당 값의 1을 더한 값이 해당 강의 Strahler 순서이다.
-> 이와 같은 방법으로 구합니다.

그렇다면, 먼저 어떤 강들이 연결되어 있는지와 X번째 강은 몇번째에 탐색을 해야하는지를 알고 있어야합니다.
-> 위상 정렬을 사용해야 합니다.

따라서, 강들의 단계를 찾은 뒤, 1번째 단계의 강부터 확인해 M번째 강까지 Strahler 순서를 갱신해 나가면 됩니다.
이때 Strahler 값의 최종 갱신은 queue에서 해당 강 번호를 pop을 한 뒤 해야합니다.
-> 만약, X번째 강에 1, 1, 2라는 Strahler 값이 순서대로 들어온다고 한다면 값이 2가 아닌 3이 되기 때문입니다.

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#define F first
#define S second

using namespace std;

int test_case;
int K, M, P;
int step[1001];
pair<int, int> Strahler[1001]; // Strahler 값, 값이 나온 횟수
vector<int> connect[1001];
queue<int> q; // 강 번호, 가장 큰 순서, 횟수 

void reset_array(){
	for(int i = 1; i <= M; i++){
		step[i] = 0;
		connect[i].clear();
		Strahler[i] = {0, 0};
	}
}

void topological_sort(){
	while(!q.empty()){
		int x = q.front();
		if(Strahler[x].S >= 2) Strahler[x] = {Strahler[x].F + 1, 1};
		q.pop();
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i];
			step[xx]--;
			// 다음 좌표를 방문할 때마다 Strahler 값을 갱신한다.
			if(Strahler[x].F > Strahler[xx].F){
				Strahler[xx] = {Strahler[x].F, 1};			}
			else if(Strahler[x].F == Strahler[xx].F){
				Strahler[xx] = {Strahler[xx].F, Strahler[xx].S + 1};
			}
			if(step[xx] == 0){
				q.push(xx);
			}
		}
	}
}

void solve(){
	for(int i = 1; i <= M; i++){
		if(step[i] == 0) {
			q.push(i);
			Strahler[i] = {1, 1};
		}
	}
	topological_sort();
	if(Strahler[M].S >= 2){
		cout << K << " " << Strahler[M].F + 1 << "\n";
	}
	else{
		cout << K << " " << Strahler[M].F << "\n";
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for(int t = 1; t <= test_case; t++){
		scanf("%d %d %d", &K, &M, &P);
		reset_array();
		for(int i = 1; i <= P; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			step[y]++;
			connect[x].push_back(y);
		}
		solve();
	}
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.