BOJ 백준 13418 : 학교 탐방하기

시작하면서

이번 문제는 최소 스패닝 트리(Minimum Spanning Tree) 카테고리 문제이다.

BOJ 13418 - 학교 탐방하기

​

문제 이해

​ 이 문제는 딱히 설명할게 없다. 오르막길은 가중치가 높은 간선, 내리막길은 가중치가 낮은 간선으로 판단하고 최소 스패닝 트리를 구성하면 문제가 해결된다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Path
{
public:
	int start, end;
	bool isUphill;

	Path(int s, int e, bool b)
	{
		this->start = s;
		this->end = e;
		this->isUphill = b;
	}
};

int FindRootParent(const vector<int>& parent, int index)
{
	if (parent[index] == index)
		return index;

	return FindRootParent(parent, parent[index]);
}

bool _AscendingCompare(const Path& a, const Path& b)
{
	if (a.isUphill == false && b.isUphill == true)
		return true;

	return false;
}

int FindSpanningTreeValue(int buildingCount, const vector<Path> &path)
{
	vector<int> parent(buildingCount);
	for (int i = 0; i < parent.size(); i++)
	{
		parent[i] = i;
	}

	int value = 0;
	for (int i = 0; i < path.size(); i++)
	{
		int startParent = FindRootParent(parent, path[i].start);
		int endParent = FindRootParent(parent, path[i].end);

		if (startParent == endParent)
			continue;

		if (startParent < endParent)
		{
			parent[endParent] = startParent;
		}
		else
		{
			parent[startParent] = endParent;
		}

		if (path[i].isUphill == true)
		{
			value++;
		}
	}

	return value;
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	int N, M;

	cin >> N >> M;

	vector<Path> path;
	int loop = M + 1;
	for (int i = 0; i < loop; i++)
	{
		int A, B;
		bool C;
		cin >> A >> B >> C;
		path.push_back(Path(A,B,!C));
	}

	sort(path.begin(), path.end(), _AscendingCompare);
	int minimumSpanningTreeValue = FindSpanningTreeValue(N + 1, path);

	reverse(path.begin(), path.end());
	int maximumSpanningTreeValue = FindSpanningTreeValue(N + 1, path);

	cout << maximumSpanningTreeValue * maximumSpanningTreeValue - minimumSpanningTreeValue * minimumSpanningTreeValue;

	return 0;
}