C++ / 21924 /도시 건설 ( 최소 스패닝 트리 )

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

문제 요약

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠습니다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했습니다.

채완이는 공사하는 데 드는 비용을 아끼려고 합니다. 

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 합니다.

위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도입니다.

그림에 있는 도로를 다 설치할 때 드는 비용은 62입니다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35입니다.

채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있습니다.

채완이를 대신해 얼마나 절약이 되는지 계산해야합니다.

문제 풀이

1. 변수들의 type을 long long int로 만들어 줍니다.

2. n과 m을 입력받습니다.

3. 부모 배열을 각각 노드가 자기자신이 부모가 되게 초기화해줍니다.

4. 그래프를 입력받습니다. 크루스칼 알고리즘을 사용하기 위해 간선을  중심으로 두개의 노드를 입력받습니다. 버리는 가중치를 구해야하기 때문에 간선의 가중치의 총합을  받아줍니다.

5. 모든 건물이 연결되어 있지 않다면 -1을 출력해야 합니다. 저는 이 부분을 dfs로 탐색하기 위해 dfs 용 그래프를 하나 더 받아줍니다. ( 양방향으로 )

6. 우선 1번노드를 시작으로 dfs탐색을 해줍니다. 탐색을 마치고 1번 노드부터 방문체크가 안되어있는 노드가 있다면 -1을 출력하고 프로그램을 종료합니다. ( 연결이 안되어있는 노드가 있는 경우임 )

7. 모든 노드가 연결되어있는 것을 확인했으면 크루스칼 알고리즘을 수행합니다. 간선 기준으로 정렬해주고 ( 가중치 기준 )

8. 현재 간선에 연결된 두 노드의 부모를 부모를 찾는 함수를 통해 부모를 찾아서 비교후 서로 다를 경우 한쪽 부모 덮어씌우기 ( 같은 트리로 만듬 ) 그리고 현재 가중치를 ( 사용하는 가중치 ) 를 더해줍니다.

9. 알고리즘을 마치면 가중치의 총합에서 사용하는 가중치를 빼서  출력합니다.

주의할 점

간선의 합이 int 최대치를 넘어갑니다.  주의해야합니다.

코드

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

using namespace std;

typedef long long int ll;
ll n, m, sum = 0, maxsum = 0;
vector<pair<ll, pair<ll, ll>>>v;
vector<ll>node[100004];
ll p[100004];
ll visit[100004];

// 부모 찾기
ll findparent(ll x)
{
	if (p[x] != x)
	{
		p[x] = findparent(p[x]);
	}
	return p[x];
}

void dfs(ll x)
{
	visit[x] = 1;
	for (ll i : node[x])
	{
		if (visit[i])
		{
			continue;
		}
		dfs(i);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
    // 부모 초기화
	for (ll i = 1; i <= n; i++)
	{
		p[i] = i;
	}

	for (ll i = 0; i < m; i++)
	{
		ll a, b, c;
		cin >> a >> b >> c;
		node[a].push_back(b);
		node[b].push_back(a);
		v.push_back({ c, {a,b} });
		maxsum += c;
	}
	// 모든 건물이 연결되어있는지 확인
	dfs(1);
	for (ll i = 1; i <= n; i++)
	{
		// 방문하지 않은 건물이 있을경우 모든 건물이 연결되어있지 않음
		if (visit[i] == 0)
		{
			cout << -1;
			return 0;
		}
	}
	// 간선 기준 ( 가중치 ) 정렬
	sort(v.begin(), v.end());
	// 크루스칼알고리즘
	for (ll i = 0; i < m; i++)
	{
		ll Aparent = findparent(v[i].second.first);
		ll Bparent = findparent(v[i].second.second);

		if (Aparent != Bparent)
		{
			p[Bparent] = Aparent;
			sum += v[i].first;
		}
	}
	// 전체 가중치에서 만들어진 스패닝 트리의 비용을 뺌
	cout << maxsum - sum;
	return 0;
}

예제 1

7 9
1 2 15
2 3 7
1 3 3
1 4 8
3 5 6
4 5 4
4 6 12
5 7 1
6 7 6

결과 1

예제 2

8 10
1 2 4
2 3 9
2 4 9
3 4 4
3 5 1
4 6 14
6 7 5
5 7 3
7 8 7
6 8 3

결과 2

예제 3

5 4
1 2 1
2 3 1
3 1 1
4 5 5

결과 3