프로그래머스_섬 연결하기

문제 : https://programmers.co.kr/learn/courses/30/lessons/42861#

코딩테스트 연습 - 섬 연결하기 | 프로그래머스

기본적으로 Kruskal 알고리즘을 통해 해결이 가능하였다.

최소 비용의 간선들만을 가져오면서 연결을 하는데 주의할 점은 Cycle을 만들지 않도록 하는 것이다.

Cycle check는 Union Find의 방식을 통해 해결이 가능하였다.

(부모까지 올라가서 부모 비교하면서 합치기)

풀이 1.

실제 이차원 vector의 graph를 만들어서 탐색하고 결과값 도출하기

답을 구할 수 있지만, 실질적으로 문제에서 주어지는 costs만을 통해 값을 구할 수 있기에 비효율적인 방식이었다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#define USED -1
using namespace std;

int get_parent(vector<int> p, int i){
    while(p[i]>0)
        i=p[i];
    return i;
}
bool cycle_check(vector<int> p, int i, int j){
    int p_i = get_parent(p,i);
    int p_j = get_parent(p,j);
    if(p_i==p_j) return true; // cycle
    else return false; // not cycle
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<int> p(n, -1);
    
    // graph 생성
    vector<vector<int>> g;
    for(int i=0;i<n;i++){
        vector<int> tmp(n,0);
        g.push_back(tmp);
    }
    // 값 받기
    for(int i=0;i<costs.size();i++){
        g[costs[i][0]][costs[i][1]]=costs[i][2];
        g[costs[i][1]][costs[i][0]]=costs[i][2];
    }
    
    int cnt=0;
    // 최단 거리 찾기
    while(cnt != n-1){
        // 최소 간선 찾기
        int min = -1, min_i, min_j;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(g[i][j] > 0 && min==-1)
                    min=g[i][j], min_i=i, min_j=j;
                else if(g[i][j]>0 && min != -1 && min > g[i][j])
                    min=g[i][j], min_i=i, min_j=j;
            }
        }
        // 사용표시
        g[min_i][min_j] = USED;
        g[min_j][min_i] = USED;
        
        // 사이클 체크
        if(!cycle_check(p,min_i,min_j)){
            // 부모 추가
            int p_i =get_parent(p,min_i), p_j = get_parent(p,min_j);
            p[p_i]= p_j;
            answer+=min;
            cnt++;
        }
    }
    return answer;
}

풀이 2.

훨씬 더 효율적인 주어진 input costs를 그대로 활용하기!

풀이의 전개과정 자체는 동일하나 자료형을 따로 구성하지 않았기에 시간적, 공간적으로 보다 효율적인 알고리즘이었다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#define USED -1
using namespace std;

int get_parent(vector<int> p, int i){
    while(p[i]>0) i=p[i];
    return i;
}
bool cycle_check(vector<int> p, int i, int j){
    int p_i = get_parent(p,i);
    int p_j = get_parent(p,j);
    if(p_i==p_j) return true; // cycle
    else return false; // not cycle
}
bool compare(vector<int> a, vector<int> b){
    return (a[2]<b[2]);
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<int> p(n, -1);
    sort(costs.begin(),costs.end(),compare);
    int now=0, cnt=0;
    
    // 탐색
    while(cnt != n-1){
        int min = costs[now][2];
        int min_i = costs[now][0], min_j = costs[now][1];
        
        // 사이클 체크
        if(!cycle_check(p,min_i,min_j)){
            // 부모 추가(i가 j보다 무조건 작으므로)
            int p_i =get_parent(p,min_i), p_j = get_parent(p,min_j);
            p[p_j]= p_i;
            answer+=min;
            cnt++;
        }
        now++;
    }
    return answer;
}