[백준 1368][💛2] 물대기 (MST, 크루스칼)

🚀 난이도

💛 골드 2

🚀 문제

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

🚀 내 풀이 ⭕

풀이 참고 : https://conkjh032.tistory.com/386

우물을 직접 판 논에서 물을 끌어와 쓰는 논들은, 우물을 직접 판 해당 논을 루트로 하는 트리에서 연결된다고 생각할 수 있다. 그러면 트리가 여러개가 될 수 있는 셈인데 어떻게 해야하지..? 라는 고민을 했었다.

고민을 하다가 구글링을 하여 다른 분의 풀이를 보았는데 생각보다 심플한 풀이였다. 가상의 노드를 하나 더 만든 후 이를 루트로 하고 우물을 직접 파는 비용도 추가하는 것이다. 이렇게 생각하면 우물을 직접 파는 비용도, 연결하는 비용도 하나의 그래프로 연결할 수 있다. 위 링크 블로그에서 그림을 보면 쉽게 이해가 될 것이다.

가상의 노드를 루트로 두고, 우물을 직접 파는 비용으로 논들과 이 루트를 연결하는 것으로 그래프를 시작한다면 하나의 그래프로 통합시킬 수 있는 셈이다.

이렇게 하나의 그래프로 만든 후 평범하게! MST 최소신장트리 알고리즘 적용하여 풀이하면 된다. 나는 크루스칼 알고리즘을 사용했다.

#include <bits/stdc++.h>

using namespace std;

struct Edge { int a, b, cost; };
bool cmp(const Edge& a, const Edge& b) { return a.cost < b.cost; }
int parent[301];

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

void union_graph(int a, int b) {
	int par_a = get_root(a);
	int par_b = get_root(b);
	if (par_a < par_b) parent[par_b] = par_a;
	else parent[par_a] = par_b;
}

bool is_same_graph(int a, int b) {
	int par_a = get_root(a);
	int par_b = get_root(b);
	if (par_a == par_b) return true;
	else return false;
}

int main() {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N;
	cin >> N;
	
	vector<Edge> edges;
	for (int i = 1; i <= N; ++i) {
		int cost;
		cin >> cost;
		edges.push_back({ 0, i, cost });
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			int cost;
			cin >> cost;

			if (i != j) 
				edges.push_back({ i, j, cost });
		}
	}

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

	for (int i = 0; i <= N; ++i)
		parent[i] = i;

	int total_cost = 0;
	for (int i = 0; i < edges.size(); ++i) {
		if (is_same_graph(edges[i].a, edges[i].b) == false) {
			union_graph(edges[i].a, edges[i].b);
			total_cost += edges[i].cost;
		}
	}
	cout << total_cost;
}

처음엔 아래와 같이 풀이를 해서 틀렸었다. 자기 자신과 연결되는 비용은 항상 0 이기 때문에 이를 피하기 위해서 저렇게 짰었던건데 이렇게 짜면 입력받는 처리가 되지 못해 뒤로 밀려서 틀린 풀이가 되버렸다. 0 도 cin 을 통해 입력 받은 후에 continue 시켰어야 했다.

	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			if (i == j) continue;
			
			int cost;
			cin >> cost;
			edges.push_back({ i, j, cost });
		}
	}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기