[C/C++] 백준 10423번 - 전기가 부족해

✏️ 문제 링크

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

10423번: 전기가 부족해

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

최소 신장 트리 구현에 관한 문제입니다.

 

가장 먼저 MST구현 반복문의 횟수 설정입니다.

원래 기존의 MST는 사용한 에지의 개수가 정점의 개수 - 1만큼 될 때가지반복문을 돌려야 하지만 위 문제의 경우에는 연결하지 않아도 되는 발전소의 개수가 주어지기 때문에 에지의 개수가 N-K가 될 때까지만 반복문을  돌리면 됩니다

 

두 번째는 두 노드를 Union하는 조건입니다.

기존에는 대표 노드가 다르면 Union을 해줬지만 이 문제는 조금 더 생각을 해봐야 합니다.

바로 두 개의 대표 노드가 모두 발전소인 경우입니다. 이 경우에는 두 개의 대표 노드가 다르더라도 굳이 연결할 필요가 없습니다. 연결하게 되면 오히려 최소비용보다 증가하게 됩니다. 그래서 두 개의 대표 노드가 다르면서 두 대표 노드 모두 발전소가 아닌 경우에만 Union을 해줍니다(하나만 발전소인 경우에는 상관이 없습니다)

 

세 번째는 구조체 설정입니다.

u,v,w를 입력받게 되는데 여기서 가중치를 기준으로 오름차순하는 구조가 될 수 있도록 구조체 Edge를 설정했고

Edge를 자료형으로 가지는 우선순위 큐를 오름차순으로 정렬하였습니다.

 

마지막으로 Union함수 설정입니다.

기본적인 Union함수에서 몇 가지 조건을 더 설정하였습니다. 

두 노드의 대표 노드가 모두 발전소인 경우 => 결합할 필요가 없습니다

두 노드의 대표 노드 중 한 개만 발전소인 경우 => 발전소를 대표 노드로 설정해줍니다.

모두 발전소가 아닌 경우 => 두 노드 중 더 작은 값을 부모 노드로 설정했습니다(굳이 안 해도 됨)

 

 

✏️ 문제 코드

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

vector<int>powerStation;
vector<int>parent;
void Union(int a, int b);
int find(int a);
int N, M, K, u, v, w,power;
typedef struct Edge {
	int u, v, w;
	bool operator > (const Edge& temp)const {
		return w > temp. w;
	}
}Edge;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> K;

	parent.resize(N + 1);
	powerStation.resize(N + 1);
	for (int i = 1; i <= N; i++)
		parent[i] = i;

	priority_queue<Edge, vector<Edge>, greater<Edge>>pq;
	
	for (int i = 0; i < K; i++) {
		cin >> power;
		powerStation[power] = 1;
	}

	for (int i = 0; i < M; i++) {
		cin >> u >> v >> w;
		pq.push(Edge{ u, v, w });
	}

	int useEdge = 0;
	int powerSum = 0;

	while (useEdge < N - K) {
		Edge now = pq.top();
		pq.pop();
		int start = now.u;
		int end = now.v;
		int value = now.w;

		int node1 = find(start);
		int node2 = find(end);
		if (node1 != node2) {
			if (powerStation[node1] == 1 && powerStation[node2] == 1)
				continue;
			else {
				Union(start, end);
				powerSum += value;
				useEdge++;
			}
		}
	}
	cout << powerSum;
}
void Union(int a, int b)
{
	int node1 = find(a);
	int node2 = find(b);

	
	if (node1 != node2) {
		if (powerStation[node1] != 1 && powerStation[node2] != 1) {
			if (node1 > node2)
				parent[node1] = node2;
			else
				parent[node2] = node1;
		}
		else {
			if (powerStation[node1] == 1)
				parent[node2] = node1;
			else
				parent[node1] = node2;
		}
		
	}
}
int find(int a)
{
	if (a == parent[a])
		return a;
	else
		return parent[a] = find(parent[a]);
}

 

 

✏️ 더 보기

https://pooreumjung.tistory.com/326

[C/C++] 백준 다리 만들기 문제 모음 / 백준 2146번, 백준 17472번

https://pooreumjung.tistory.com/302

Algorithm 공부 #18 - 그래프(최소 신장 트리)