[C++] 백준 13418번: 학교 탐방하기

문제 링크

13418번: 학교 탐방하기

문제 요약

학생들이 학교 탐방을 하는데, 경로 상에 오르막길이 있다면, (오르막길 사용 횟수)$^2$ 만큼 피로도가 쌓이게 된다. 단, 한 번 이용한 오르막길을 다시 방문한다고 해도 횟수는 증가하지 않는다.
이때, 오르막길을 최대한 많이 이용하는 경로와 최소로 이용하는 경로 사이의 피로도 차이를 구해야 한다.

접근 방법

크게 고민할 것이 없는 간단한 최소 스패닝 트리 문제입니다. 크루스칼 알고리즘을 통해서 풀었습니다.

1. 입력 받은 간선들을 모두 벡터에 저장해 주고, 오르막길인 간선이 앞에 오도록 정렬합니다. 그리고 크루스칼 알고리즘을 통해서 최소 스패닝 트리를 만들면서 오르막길의 사용 횟수를 카운트 해줍니다.
2. 이번엔 내리막길인 간선이 앞에 오도록 정렬합니다. 다시 크루스칼 알고리즘을 통해서 최소 스패닝 트리를 만들면서 오르막길 사용 횟수를 카운트 해줍니다.
3. 두 사용 횟수를 제곱한 값의 차를 출력해줍니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Edge {
	int v1, v2, flag;
};

const int MAX = 1001;
int n, m, parent[MAX];
vector<Edge> edges;

bool compare1(const Edge& a, const Edge& b) {
	return a.flag < b.flag;
}

bool compare2(const Edge& a, const Edge& b) {
	return a.flag > b.flag;
}


void init(void) {
	for (int i = 0; i < MAX; i++) parent[i] = i;
}

int Find(int a) {
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b) {
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m;

	for (int i = 0; i < m + 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({a, b, c});
	}

	init();

	sort(edges.begin(), edges.end(), compare1);

	int ans1 = 0, ans2 = 0;
	for (auto& edge : edges) {
		if (Find(edge.v1) != Find(edge.v2)) {
			Union(edge.v1, edge.v2);

			if (!edge.flag)
				ans1++;
		}
	}

	init();

	sort(edges.begin(), edges.end(), compare2);

	for (auto& edge : edges) {
		if (Find(edge.v1) != Find(edge.v2)) {
			Union(edge.v1, edge.v2);

			if (!edge.flag)
				ans2++;
		}
	}

	cout << (int)(pow(ans1, 2) - pow(ans2, 2)) << '\n';
	return 0;
}