14621 나만 안되는 연애

그래프의 최단 거리를 구해야 하기 때문에 MST를 사용하면 되겠다 싶었다. 그런데 MST를 일년 전에 공부했고 자료도 정리해놓지 않아서.... 다시 이해하는데 오래 걸렸다. 그리디하게 가장 edge를 구해놓고 가장 짧은 것부터 뽑아서 계산한다. Union Find로 해당 간선이 이미 계산된 간선인지 확인한다. 

 

 

코드는

1. 학교 입력 받으면서 유파 초기화

2. 여-남 경우에만 간선을 추가한다

3. 간선을 오름차순으로 정렬한다 -> 그리디하게 가장 짧은 것부터 뽑기 위해서

4. 가장 짧은 길이부터 뽑아서 더한다, 간선을 몇 개 더했는지도 계산한다

5. 간선이 n - 1개가 아닌 경우 노드를 전부 확인 안 했으니 -1을 출력한다

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

i64 p[1010];

int Find(int a) {
    if(p[a] == a)
        return a;
    return p[a] = Find(p[a]);
}

int Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);
    
    if (px == py)
        return 0;
    p[px] = py;
    return 1;
}

bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
    return p1.second < p2.second;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    vector<string> school(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> school[i];
        p[i] = i; // UnionFind 초기화
    }
    
    vector<pair<ii, int>> v;
    for (int i = 0; i < m; i++) {
		int from, to, d;
		cin >> from >> to >> d;
		if (school[from] != school[to]) // 조건에 일치하는 경우에 간선 추가ㅁ
		    v.push_back({{from, to}, d});
	}
	
    int schoolCnt = 0;
    int ans = 0;
    
    sort(all(v), cmp);
    
    for (auto edge: v) {
        if (Union(edge.xx.xx, edge.xx.yy) == 0)
            continue;
        
        ans += edge.yy;
        schoolCnt++;
    }
    
    if (schoolCnt == n - 1)
        cout << ans << "\n";
    else
        cout << "-1\n";
    
    return 0;
}

 

아래는 북님 코드 염탐

 

 

 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

struct Edge {
    int u, v, d;
};

int par[1005];

int find(int x) {
    if (x == par[x])
        return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    par[x] = y;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> type(n + 5);
    
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        type[i] = s == "M";
        par[i] = i;
    }
    
    vector<Edge> edge;
    for (int i = 0; i < m; i++) {
        Edge e;
        scanf("%d %d %d", &e.u, &e.v, &e.d);
        if (type[e.u] == type[e.v])
            continue;
        edge.push_back(e);
    }
    
    sort(all(edge), [](const Edge& l, const Edge& r) {
        return l.d < r.d;
    });
    
    int used = 0;
    int ans = 0;
    for (auto &e: edge) {
        if (find(e.u) == find(e.v))
            continue;
        used++;
        ans += e.d;
        merge(e.u, e.v);
    }
    
    if (used != n - 1) {
        printf("-1\n");
        return 0;
    }
    
    printf("%d\n", ans);
    return 0;
}