[CSES] Road Reparation

https://cses.fi/problemset/task/1675/

CSES - Road Reparation

 

 

망할 알고리즘 응용 덕분에 크루스칼 제대로 머리에 기억 남을 듯 하다. 물론 얼마나 갈지는 모르겠지만. 

 

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

using namespace std;

vector<pair<long long int, pair<long long int, long long int> >> Edge;

class UFDS {
private:
    vector<int> p, rank, setSizes;
    int numSets;
public:
    UFDS(int N) {
        numSets = N;
        rank.assign(N, 0);
        p.assign(N, 0);
        for (int i = 0; i < N; i++) p[i] = i;
        setSizes.assign(N, 1);
    }
    int findSet(int i) {
        return (p[i] == i) ? i : p[i] = findSet(p[i]);
    }
    bool isSameSet(int i, int j) {
        return findSet(i) == findSet(j);
    }
    void unionSet(int i, int j) {
        if (!isSameSet(i, j)) {
            int x = findSet(i), y = findSet(j);
            if (rank[x] > rank[y]) {
                setSizes[findSet(x)] += setSizes[findSet(y)];
                p[y] = x;
            }
            else {
                setSizes[findSet(y)] += setSizes[findSet(x)];
                p[x] = y;
                if (rank[x] == rank[y])
                    rank[y]++;
            }
            numSets--;
        }
    }
    int setSize(int i) {
        return setSizes[findSet(i)];
    }
    int numDisjointSets() {
        return numSets;
    }
};

int main(void) {
    long long n, m;
    cin >> n >> m;
    long long  total_weight=0;
    long long  edge_check = 0;

    UFDS UF(n+1);
    for (int i = 0; i < m; i++) {
        long long weight;
        int v1, v2;
        cin >> v1 >> v2 >> weight;
        Edge.push_back(make_pair(weight, make_pair(v1, v2))); 
        //((v1,v2) , 가중치) 형태로 저장하는 pair를 edge에 저장한다.
    }
    sort(Edge.begin(), Edge.end()); // 저장한 edge들을 정렬한 후 union_find를 실행한다.

    for (int i = 0; i < m; i++) {
        if (!UF.isSameSet(Edge[i].second.first, Edge[i].second.second)) {
            //같은 부모 아래 있지 않은 vertex들을 union한다.
            UF.unionSet(Edge[i].second.first, Edge[i].second.second);
            total_weight += Edge[i].first;
            //union한 edge의 가중치를 저장한다.
            edge_check++;
            // spanning tree의 연결 된 edge 개수가 n-1개임을 체크하기 위해 edge_check를 1 증가한다.
        }

    }
    if (edge_check == n-1) {
        //edge_check의 개수가 n-1개가 되어 spanning tree가 완성 되면 최소 가중치를 출력한다.
        cout << total_weight;
    }
    else { // 그렇지 않으면 impossible을 출력한다.
        cout << "IMPOSSIBLE";
    }
}

위의 코드는 Union Find 클래스를  사용하여 구현 한 것이다.

 

비슷한 느낌으로 class 없이 구현한 경우

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

#define endl "\n"
#define MAX 100000+1
using namespace std;

int N, M, MST;
int parent[MAX];
vector<pair<int, pair<int, int> >> Edge;
// 가중치 ,(vertex_a, vertex_b) 형태로 저장하는 pair 선언

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

void union_edge(int x, int y) {
	x = Find_parent(x);
	y = Find_parent(y);
	if (x != y) parent[y] = x;
}

bool isSameParent(int x, int y) {
	x = Find_parent(x);
	y = Find_parent(y);
	if (parent[x] == parent[y]) return true;
	else return false;
}
int main(void) {
	int n, m;

	cin >> n >>m; // 컴퓨터 개수
	//cin >> m; // edge 개수

	for (int i = 0; i < m; i++) {
		int weight, v1, v2;
		cin  >> v1 >> v2 >> weight;
		Edge.push_back(make_pair(weight, make_pair(v1, v2)));
	}
	sort(Edge.begin(), Edge.end());

	for (int i = 0; i < m; i++) {
		parent[i] = i;
	}
	
	for (int i = 0; i < m; i++) {
		if (isSameParent(Edge[i].second.first, Edge[i].second.second) ==false)
		{
			union_edge(Edge[i].second.first, Edge[i].second.second);
			MST += Edge[i].first;
		}
	}
	cout << MST;
}

이러한 경우가 있다. 아래 코드는 변수 선언 범위에서 오류가 나므로 제출 시에 int 값을 더 큰 범위의 값으로 변경 해 주어야 한다. 

 

이와 동시에 백준에도 주제만 다르지 동일한 문제가 있어서 끌고 온다.

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

1922번: 네트워크 연결

 

• Vector와 Pair를 사용하고 접하는 데에 두려움이 조금 줄었.땨.
• 예전에는 Union find 얘기만 들었어도 치를 떨었는데 그래도 이번 기회로 조금 덜 미워하게 될 수도...?
• 사실 위 코드인 Union find class로 구현되어 있는 것은 Class 자체를 내가 구현한 게 아니라서 조금 낯설긴 했지만 저렇게도 구현할 수 있구나 싶어서 새로운 경험이었다.
• 두번째 코드가 직접 구현한 것인데 이전에 크루스칼 알고리즘에 대해 한 번 훑고 문제 풀이를 진행하니까 그래도 좀 덜 겁먹은 것 같다.
• https://dusty-wznt.tistory.com/50