[L3] 프로그래머스 섬 연결하기 C++ MST, 최소 신장 트리, 유니온 파인드

리뷰

프로그래머스

 

알고리즘 고득점 Kit 그리디에서 왜 MST가 나오는지는 모르겠지만 기본적인 문제라 쉽게 풀었다.

 

 

전역 변수

• nodes : 유니온 파인드를 통해 섬의 그룹화를 하기 위한 정수형 배열, 크기는 섬의 최대 100으로 설정한다.
• Bridge : 간선 정보를 저장하기 위한 구조체, 내부적으로 sort를 해주어야 하니 내부에 cmp함수를 작성한다.

 

함수

1. Find

int Find(int a)

 

매개변수로 받은 노드의 그룹 정보를 찾기 위한 함수

1. 매개변수로 노드 번호를 변수 a로 받아준다.
2. nodes배열의 a인덱스가 a라면 a를 리턴해 준다.
3. nodes배열의 a인덱스가 a가 아니라면 nodes[a]를 Find함수의 매개변수로 전달하고 해당 값을 저장한다.
4. 결국 재귀를 진행하면서 동시에 다른 노드의 부모 정보까지 최신화 해주는 경로 압축을 진행한다.

2. Union

bool Union(int a, int b)

 

두 노드 a, b의 그룹을 합쳐주는 함수

1. Find 함수를 통해 a, b 각각 속한 그룹 정보를 구해 정수형 변수 A, B에 저장해 준다.
2. 만약 A와 B가 동일하다면 이미 같은 그룹에 존재하는 것이기 때문에 false를 리턴해 준다.
3. 같은 그룹이 아니라면 nodes배열의 인덱스 B의 값을 A로 변경해 주고 true를 리턴해 준다.

 

문제풀이

1. 노드의 개수 n만큼 for문을 개행하고, nodes의 i번째 인덱스의 값에 i를 할당해 준다.
2. Bridge타입 벡터 lst를 초기화 해주고, consts개의 간선을 모두 벡터에 push해준다.
3. lst벡터를 간선의 비용을 기준으로 오름차순으로 정렬해 준다.
4. 모든 간선을 순회하며 각 다리를 Union해주고 Union에 성공했다면 answer에 다리의 가중치를 더해준다.
5. 작업을 마친 뒤 answer에 저장된 값을 리턴해 준다.

 

참고 사항

Union함수 내부에서 Find함수가 돌아가기 때문에 Find함수는 Union내부에서만 처리해 주면 된다.

대신 Union을 bool타입으로 리턴하여 성공 여부를 알려줘야 한다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int nodes[100];
struct Bridge {
    int cur, next, w;
    bool operator<(const Bridge& other) const {
        return w < other.w;
    }
};

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

bool Union(int a, int b) {
    int A = Find(a);
    int B = Find(b);
    if (A == B) return false;
    nodes[B] = A;
    return true;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for (int i = 0; i < n; i++) nodes[i] = i;
    
    vector<Bridge> lst;
    for (int i = 0; i < costs.size(); i++) {
        lst.push_back({costs[i][0], costs[i][1], costs[i][2]});
    }
    sort(lst.begin(), lst.end());
    
    for (int i = 0; i < lst.size(); i++) {
        Bridge bridge = lst[i];
        if (Union(bridge.cur, bridge.next)) answer += bridge.w;
    }
    
    return answer;
}