[백준] 13418번 - 학교 탐방하기 (C++) 문제 및 풀이

문제) 백준 - 최소 스패닝 트리 - 학교 탐방하기

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

13418번: 학교 탐방하기

 

내리막길로 갈 수 있는 최대 간선과 오르막길로 갈 수 있는 최대 간선의 차를 구하는 문제입니다. 모든 점을 잇는 간선을 뽑아야하므로 최소 스패닝 트리를 이용하여 간선을 선택합니다. 최대 간선은 정렬을 반대로 하여 Kruskal 알고리즘을 진행합니다.

 

C++ 소스코드)

	bool cmp1(coords a, coords b){
	return a.c < b.c;
	}
	bool cmp2(coords a, coords b){
	return a.c > b.c;
	}
	int find(int u){
	if(u == parent[u]) return u;
	return parent[u] = find(parent[u]);
	}
	void merge(int u, int v){
	u = find(u); v = find(v);
	if(u == v) return;
	parent[u] = v;
	}
	int kruskal(){
	for(int i = 0; i <= N; ++i)
	parent[i] = i;
	int ans = 0, cnt = 0;
	for(auto a : graph){
	if(find(a.a) != find(a.b)){
	merge(a.a, a.b);
	if(a.c == 0) ans++;
	if(++cnt == N) break;
	}
	}
	return ans * ans;
	}

view raw 13418.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/13418_%ED%95%99%EA%B5%90%ED%83%90%EB%B0%A9%ED%95%98%EA%B8%B0.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions