c++ 알고리즘 스터디 2주차 - 크루스칼 알고리즘

크루스칼 알고리즘 (Kruskal algorithm)

스터디장님 설명듣고 동빈나 블로그 보고 크루스칼 알고리즘 복습함

(m.blog.naver.com/ndb796/221230994142) 갓동빈님 

 

1. 간선의 크기만큼 그래프를 생성한다. 

2. 각 간선에는 연결된 노드들이 적혀있다.

3. 간선들을 오름차순으로 정리한다.

4. 간선 값이 가장 작은 녀석부터 이어간다. 
여기서 유니온파인드를 이용한다. 

5. 만약 간선의 두 노드가 이미 연결되어있다면 SKIP 해버린다.

→ 왜? 오름차순으로 정렬된 상태에서 진행되기때문에 만약 연결되어있었다면 이전의 간선 값이 더 작을 것이기 때문이다. 

6. 모든 부모노드가 1이 되면 (꼭 1일 필요없음 그냥 연결만 되면 됨) 끝내버린다.

 

이걸 코드로 구현을 해보자 

백준 1197번 (www.acmicpc.net/problem/1197 ) 문제 풀면서 구현해봄 

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

using namespace std;
vector<int> parent;
vector<pair<int, pair<int, int>>> edges; //[1,[2,3]] 형태의 그래프 생성

//부모찾기
int getparent(vector<int>& parent , int x){
    if (parent[x] == x) return x;
    return parent[x] = getparent(parent, parent[x]);
}

//부모 합치기 
void unionparent(vector<int>& parent, int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x < y)parent[y] = x;
    else parent[x] = y;
}

int find(vector<int>&parent , int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x == y) return 1;
    else return 0;
}


int main() {
    //정점, 간선 개수 입력받음
    int v, e;
    scanf("%d %d", &v, &e);

    //부모배열의 크기 resize
    parent.resize(v + 1);
    // 부모 배열 초기화
    for (int i = 1; i <= v; i++)   parent[i] = i;

    // 1. 간선의 크기만큼 그래프를 생성
    // edges.resize(e);

    // 2.[거리 ,[시작노드, 끝노드]] 순으로 그래프에 넣어주기
    for (int i = 0; i < e; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edges.push_back(make_pair(c, make_pair(a, b))); //make_pair(a,b) : a,b가 들어간 pair를 만들어준다
    }
    // 3.그래프의 가중치를 오름차순으로 정리한다.
    sort(edges.begin(), edges.end());

    int sum = 0; //가중치를 합하자

    //4. 간선값이 가장 작은 녀석부터 이어간다 
    for (int i = 0; i < e; i++) {
        //시작노드와 끝노드가 이미 합집합이라면!??!??! 이미 이어진거니까 최소비용이 아니다! 넘겨버리자.
        if (!find(parent, edges[i].second.first, edges[i].second.second)) {

            // 시작 노드와 끝노드를 합집합하자. => union 사용
            unionparent(parent, edges[i].second.first, edges[i].second.second);

            // 시작노드와 끝노드가 합집합이라는건 길이 연결됐다는 뜻이므로 가중치를 더해주자.
            sum += edges[i].first;
        }
    }

    printf("%d", sum);
}

여기서 시간을 좀 끈 게 40번째 줄에서 resize를 했는데 하니까 입력을 못받았다. 

스터디장님 말로는 push_back이 공간을 하나하나 늘려주며 입력받는거라서 resize를 하면 안된다고하심. ㅎㅅㅎ 

 

 

백준 14621번 나만 안되는 연애(www.acmicpc.net/problem/14621)

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

using namespace std;
vector<int> parent;
vector<int>group;
vector<pair<int, pair<int, int>>> edges;

int getparent(vector<int>& parent , int x){
    if (parent[x] == x) return x;
    return parent[x] = getparent(parent, parent[x]);
}

void unionparent(vector<int>& parent, int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x < y)parent[y] = x;
    else parent[x] = y;
}

int find(vector<int>&parent , int x, int y) {
    x = getparent(parent, x);
    y = getparent(parent, y);
    if (x == y) return 1;
    else return 0;
}

int main() {
    int n,m;
    scanf("%d %d", &n, &m);
    parent.resize(n + 1);
    group.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        char sex;
        cin >> sex;
        if (sex == 'M') group[i] = 1;
        else group[i] = 2;
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (group[a] != group[b])
            edges.push_back(make_pair(c, make_pair(a, b))); 
        else edges.push_back(make_pair(1001, make_pair(a, b)));
        //group이 같으면 성별이 같다는 뜻이다. 이때의 간선은 쓰이지 않으므로 우선 최댓값인 1000을 넘는 1001을 지정해주었다.
    }
    sort(edges.begin(), edges.end());
    int sum = 0; 
    for (int i = 0; i < m; i++) {
    //거리가중치값이 1000보다 크면 성별이 같다 즉 안쓰는 간선이라는 뜻이므로 1000보다 작거나 같을 때만 고려해줌
        if (edges[i].first < 1001) {
            if (!find(parent, edges[i].second.first, edges[i].second.second)) {
                unionparent(parent, edges[i].second.first, edges[i].second.second);
                sum += edges[i].first;
            }
        }
    }
    for (int i = 1; i < n; i++) {
        if (!find(parent, i, i + 1)) {
            sum = -1;
            break;
        }
    }
    printf("%d", sum);
}

처음에 별 생각없이 풀었는데 생각보다 복병?이 많았다. 

1. 성별이 뭐가 중요하지? 싶었는데 그림을 제대로 보니까 성별이 같으면 이어주지를 않는다ㅜㅜ 즉 같은 성별끼리에서 나오는 간선은 사용하지 않는 다는 것이다. 

→ 성별에 대해서 배열을 만든 후 성별이 같다 = 즉 배열값이 같다면 거리값을 최댓값인 1000보다 더 큰 1001 을 주었다.  이후 unionfind를 실행할 때 성별이 같은 간선은 쓰지 않기 위해 거리값이 1000보다 작거나 같을때만 고려해주었다.

 

2. parent[1] 값과 다른 parent값들이 같으면 된다고 생각함. 

진짜 어리석은 생각이었다 만들어놓은 find함수를 써먹으면 되는데,,,, 

이 방법이 안되는 이유는 이렇다 백준에서 주어진 예제대로 하면 맨 마지막 부모배열은 

1	2	3	4	5
1	1	1	2	2

이렇게 된다. 4,5번째가 부모노드를 2로 가지고 있었는데 맨 마지막에 2번째가 부모노드를 1로 가지면서 

4,5번째가 업데이트가 안되는거다... 

→ 그냥 깔끔하게 find 함수 써서 해결,,,,, 

 

3. 런타임에러가 난다. 

원래는 맨마지막 부분에 이런식으로 부모노드가 같지 않은 녀석이 있으면 바로 -1을 리턴하게 만들어주었는데 런타임에러가 자꾸난다. 

 for (int i = 1; i < n; i++) {
        if (!find(parent, i, i + 1)) return -1;
        }

그래서 검색을 해보았더니 나같이 런타임에러가 나오는 사람이 왜나는지 질문을 했고 고수분들이 런타임에러가 나는 몇가지 이유에 대해서 적어놔주셨다 ( www.acmicpc.net/board/view/22980 ) 

main함수에서는 0이 아닌 다른 걸 return하면 런타임에러가 뜬다고한다,,,, ㅠㅠ 신기하네