[C++] 백준 10423 : 전기가 부족해

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

10423번: 전기가 부족해

백준 10423번 전기가 부족해 문제를 풀었다.

 

최소 비용으로 연결하는 문제라서 크루스칼 알고리즘을 사용했다.

 

plant 배열은 발전소 도시의 숫자를 저장한다.

city 배열은 도시의 숫자와 전기가 공급됐는지 체크해주는 변수를 저장한다.

graph 배열은 BFS 탐색용이다.

우선순위 큐와 parent 배열은 크루스칼 알고리즘용이다.

 

먼저 입력을 받으면서 city배열을 초기화해준다.

크루스칼을 실행하는데 start노드와 end노드의 상태를 매번 확인해줬다.

start노드와 end노드 둘 다 전기가 공급된 상태라면 continue를 사용해서 연결을 건너 뛰었다.

 

둘 중 하나라도 전기 공급이 안된 상태라면 두 노드를 연결했을 때 사이클이 형성되는지 체크한다.

사이클이 형성되지 않는다면 두 노드를 연결하고 BFS탐색을 위해 graph에 두 노드를 넣는다.

그 다음에 BFS탐색을 실행한다. 처음에 BFS의 큐에 plant에 있는 발전소 도시를 넣어서 초기화해주고 BFS를 실행한다. 발전소 도시와 인접한 도시들의 전기 공급 상태를 갱신해가면서 탐색한다.

탐색이 끝났을 때 모든 도시에 전기가 공급되었다면 true를 반환하고 한 도시라도 전기 공급이 안되었다면 false를 반환한다.

 

크루스칼에서 BFS탐색 결과를 true로 받았으면 더 이상 알고리즘을 수행할 필요가 없다. 최소 비용을 출력하고 함수를 종료하면 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;

#define INF 1000000000
#define LLINF 9223372036854775800

struct Edge {
	int start;
	int end;
	int cost;
};

struct Node {
	int num;
	bool electric;
};

struct compare {
	bool operator()(Edge a, Edge b) {
		return a.cost > b.cost;
	}
};

int n, m, k;
vector<int> plant;
vector<Node> city;
vector<int> graph[1001];
priority_queue<Edge,vector<Edge>,compare> pq;
int parent[1001];
int MST_cost;

bool All_supplied() {
	queue<int> q;
	int visit[1001];
	memset(visit, 0, sizeof(visit));

	for (int i = 0; i < plant.size(); i++)
		q.push(plant[i]);

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i];
			if (visit[next] == 0) {
				visit[next] = 1;
				city[next].electric = 1;
				q.push(next);
			}
		}
	}

	int flag = 0;
	for (int i = 1; i <= n; i++) {
		if (city[i].electric == 0) {
			flag = 1;
		}
	}

	if (flag)
		return false;
	else
		return true;
}

int findParent(int x) {
	if (parent[x] == x)
		return x;
	return parent[x] = findParent(parent[x]);
}

void unionParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x < y)
		parent[y] = x;
	else
		parent[x] = y;
}

bool isCycle(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return 1;
	else
		return 0;
}

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

	while (!pq.empty()) {
		Edge temp = pq.top();
		int start = temp.start;
		int end = temp.end;
		int cost = temp.cost;
		pq.pop();

		if (city[start].electric == 1 && city[end].electric == 1)
			continue;
		
		if (isCycle(start, end) == 0) {
			unionParent(start, end);		
			graph[start].push_back(end);
			graph[end].push_back(start);

			int flag = All_supplied();

			//cout << start << ' ' << end << ' ' << flag << "\n";
			
			MST_cost += cost;

			if (flag) {
				cout << MST_cost;
				return;
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;

	for (int i = 0; i <= n; i++) {
		city.push_back({ i,0 });
	}

	for (int i = 0; i < k; i++) {
		int p;
		scanf("%d", &p);
		plant.push_back(p);
		city[p].electric = 1;
	}

	for (int i = 0; i < m; i++) {
		int start, end, cost;
		scanf("%d %d %d", &start, &end, &cost);
		pq.push({ start,end,cost });

	}

	Kruskal();

	return 0;
}