[백준][크루스칼] 1197 최소 스패닝 트리 c++ 구현

목차

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

1197번: 최소 스패닝 트리

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

보기 전에 참고하면 좋을 것 같습니다

https://be-senior-developer.tistory.com/29

[Union find] c++ 구현 및 설명

 

 

 

문제 풀이 시 주의할 점

메모리 초과 오류가 발생하니 최대한 메모리를 덜 사용해 주어야 한다...

그래서  pair<long long int, pair<int, int>> 를 사용해 주어 최대한 메모리를 아꼈다.

 

 

 

잘못된 코드

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

using namespace std;

vector<pair<long long int, long long int>> edges;
vector<pair<int, int>> Nodes;
vector<int>parent;

long long int V, E;

//union find
int find_root(int node) {   //루트 노드 찾기
	if (node == parent[node])
		return node;
	return parent[node] = find_root(node);
}

void merge_root(int node1, int node2) {  //트리 통합 함수
	int root1 = find_root(node1);
	int root2 = find_root(node2);

	if (root1 != root2) {
		parent[root1] = root2;
	}

}

//union find를 이용한 크루스칼 알고리즘 구현
void kruskal() {
	int i, sum = 0, cnt = 0;
	for (i = 0; i < edges.size(); i++) {
		pair<long long int, long long int> cur = edges[i];
		int node1 = Nodes[cur.second].first;
		int node2 = Nodes[cur.second].second;

		if (find_root(node1) == find_root(node2))   //루트 노드같으면 패스
			continue;

		merge_root(node1, node2);   
		sum += cur.first;   //다를 경우 경로 합추가
		cnt++;
		if (cnt == V - 1)   //간선 다 추가될시 종료
			break;
	}
	cout << sum;

}


int main() {
	long long int A, B, C, i;
	cin >> V >> E;

	for (i = 0; i < E; i++) {
		cin >> A >> B >> C;
		edges.push_back(make_pair(C, i));  //간선과 인덱스 저장
		Nodes.push_back(make_pair(A, B));  // 노드들 저장
	}
    
	sort(edges.begin(), edges.end());  //간선 정렬
    
	for (i = 0; i <= V; i++) {
		parent.push_back(i);
	}
    
	kruskal();

}

 

 

 

 

 

올바른 코드 구현

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

using namespace std;
typedef pair<long long int, pair<int, int>> p;
long long int V, E;
vector <int> parent;
vector<p> edges;

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

void merge_root(int x, int y) {
    x = find_root(x);
    y = find_root(y);

    if (x != y) parent[y] = x;
}


//선택되지 않은 간선들 중 최소 가중치인 간선을 선택한다.

//만약 그 간선을 선택했을 때, 지금까지 구성된 스패닝 트리에 사이클이 없을 경우에만 선택한다.

//총 V - 1(정점의 개수 - 1)개의 간선이 선택될 때까지 반복한다.


void kruskal() {
    int sum = 0, cnt =0;
    for (int i = 0; i < edges.size(); i++) {
        p cur_edge = edges[i];

        //현재 간선의 두 정점
        int node1 = cur_edge.second.first;
        int node2 = cur_edge.second.second;

        //Union-Find로 사이클이 발생하는지 확인
        if (find_root(node1) == find_root(node2)) continue;        //사이클이 발생한다면 선택하지 않음

        
        sum +=cur_edge.first;
        cnt++;
        //츠리 합쳐줌
        merge_root(node1, node2);

        //만약 정점 개수 v에 대해 v - 1개의 간선을 찾았다면 종료
        if (cnt == V - 1)
            break;
    }
    cout << sum;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
    long long int A, B, C, i;
    cin >> V >> E;
    for (i = 0; i < E; i++) {
        cin >> A >> B >> C;
        edges.push_back({ C, {A, B} });
    }
    
    sort(edges.begin(), edges.end());
    
    for (i = 0; i <= V; i++) {
        parent.push_back(i);
    }

    kruskal();


}

 

 

 

참고

https://4legs-study.tistory.com/111

최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm)