[G3] 백준 9470번 Strahler 순서 C++ 위상 정렬, 트리 맵

리뷰

 

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

물이 가장 많이 고이는 노드의 값을 구하는 문제

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 변수
• k : 테스트 케이스의 번호를 저장할 변수
• m : 노드의 개수를 저장할 변수
• p : 간선의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. t값을 입력 받고, t번의 while 문을 수행해 준다.
2. 매 테스트 케이스 마다 k, m, p에 값을 입력 받고, 2차원 벡터 edges배열을 m + 1크기로 초기화 한다.
3. p개의 간선 정보를 입력 받아 edges벡터에 추가해 준다.
4. 정수형 벡터 cnt를 m + 1크기로 초기화 한다.
5. 1번 부터 m번 노드까지 순회하며 인접 리스트에 저장된 노드의 cnt를 1만큼 증가시켜 준다.
6. 정수형 큐 q를 초기화 하고, 트리 맵 벡터 maxdic을 m + 1, 정수형 벡터 strahler를 m + 1크기로 초기화 한다.
7. 1부터 m번 노드를 순회하며 cnt가 0인 노드의 번호를 q에 push해주고, maxdic의 1의 값을 1로 저장한다.
8. q가 빌 때 까지 while 루프를 순회하며 매 루프마다 요소를 한개씩 꺼내어 준다.
9. 현재 노드의 maxdic의 가장 큰 요소의 개수의 이터레이터를 변수 it에 저장해 준다.
10. 만약 해당 요소의 개수가 2개 이상이라면 변수 max_val에 키값 +1, 아니라면 키값으로 저장한다.
11. 현재 노드의 인접 리스트를 순회하며 대상의 max_val의 개수를 증가시켜 준다.
12. 대상의 cnt를 1만큼 감소시키며 만약 0이 된 경우 q에 push해준다.

 

트러블 슈팅

1. map을 사용하지 않고, 그냥 최대값만 갱신하고 만약 동일한 값이 들어오면 해당 값을 증가시키는 로직을 구현했다.
2. 하지만 1, 1, 2가 주어질 경우 답은 2가 되어야 하지만 해당 로직은 3이 만들어졌다.
3. 따라서 map을 통해 오름차순은 유지하되 개수를 정확히 골라서 최적해를 구현하였다.

 

참고 사항

• 현재 노드로 올 수 있는 모든 경우를 확인한 뒤에 Strahler를 갱신해 주어야 한다.

 

정답 코드

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

int t, k, m, p;

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

	cin >> t;
	while (t--) {
		cin >> k >> m >> p;
		vector<vector<int>> edges(m + 1);
		while (p--) {
			int a, b; cin >> a >> b;
			edges[a].push_back(b);
		}

		vector<int> cnt(m + 1);
		for (int i = 1; i <= m; ++i) {
			for (int j : edges[i]) cnt[j]++;
		}

		queue<int> q;
		vector<map<int, int>> maxdic(m + 1);
		vector<int> strahler(m + 1);
		for (int i = 1; i <= m;++i) {
			if (!cnt[i]) {
				q.push(i);
				maxdic[i][1] = 1;
			}
		}
		
		while (!q.empty()) {
			int cur = q.front(); q.pop();
			auto it = --maxdic[cur].end();
			int max_val;
			if ((*it).second >= 2) max_val = (*it).first + 1;
			else max_val = (*it).first;
			strahler[cur] = max_val;

			//cout << "cur node : " << cur << ", edges : ";
			for (int i : edges[cur]) {
				//cout << i << " ";
				maxdic[i][max_val]++;
				if (!--cnt[i]) q.push(i);
			}
			//cout << "\n";
		}

		//for (int i = 1; i <= m; ++i) cout << "node " << i << " strahler : " << strahler[i] << "\n";
		cout << k << " " << strahler[m] << "\n";
	}
}