1922번

1922번 - 네트워크 연결

MST 를 공부하면서 크루스칼 알고리즘을 배우고 풀어보았다.

크루스칼을 공부하고, sorting을 따로 하지 않으려고 map 과 iterator 를 이용해서 문제를 풀었다.

처음에는 간선이 N-1 개 일때 나와야하는데 M-1 일때 나오는 조건문을 써서 틀렸다.

두번째에는 map 은 중복적용이 되지 않는 다는 점을 잊고 map 을 사용하다가 틀렸습니다가 나왔다.

그래서 중복을 허용하는 multimap 을 이용해서 문제를 풀어서 맞을 수 있었다.

그 과정에서 구조체를 써서 문제를 풀어보았다. 평상시에 구조체를 잘 안쓰는데, 쓰면 편리한거 같다.

<정답 코드>

#include<iostream>
#include<algorithm>
#include<map>
 
using namespace std;
int p[1001];
 
typedef struct pr
{
    int x;
    int y;
}pr;
int find(int x)
{
    if (p[x] == x)
    {
        return x;
    }
    else
    {
        return p[x] = find(p[x]);
    }
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
 
    if (x == y)
    {
        return;
    }
 
    p[y] = x;
    return;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    multimap<int, pr> v;
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
    }
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        v.insert(pair<int, pr>({ c, { a,b } }));
    }
    int ans = 0;
    int cnt = 0;
    multimap<int,pr>::iterator iter;
    for (iter = v.begin(); iter != v.end(); iter++)
    {
        int x = (*iter).second.x;
        int y = (*iter).second.y;
 
        if (find(x) == find(y))
        {
            continue;
        }
 
        merge(x, y);
        cnt++;
        ans += (*iter).first;
 
        if (cnt == n - 1)
        {
            break;
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}