프로그래머스 섬 연결하기

문제 URL : programmers.co.kr/learn/courses/30/lessons/17685

코딩테스트 연습 - [3차] 자동완성

 

문제접근법 : 아래그림처럼 최소스패닝 트리를 만드는 기본적인 문제입니다.

최소스패닝 트리를 만드는 좋은 예

 

kruskal을 사용하거나 prim을 사용하든 sollin을 사용하든 상관없고 저는 kruskal 알고리즘을 사용해서

간단히 풀었습니다.

 

소스코드:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

//By 콩순이냉장고 #include <iostream> #include <vector> #include <string> #include <cstring> #include <algorithm> using namespace std; typedef pair<int, int> p; vector<pair<int, p>> v; int parent[101]; int find(int idx){//부모를 찾는함수     if (parent[idx] == idx)         return idx;     return parent[idx] = find(parent[idx]); } int kruskal(){     int sum = 0;     for (int i = 0; i < v.size(); i++)     {         int idx1 = find(v[i].second.first);         int idx2 = find(v[i].second.second);         if (idx1 != idx2)//부모가 다르다면 union시켜줘야함         {             sum += v[i].first;//합친것의 비용을 더해줌             parent[idx2] = idx1;//같은 부모를 가리키게되면 union됨         }     }     return sum; } int solution(int n, vector<vector<int>> costs) {          int answer = 0;     for (int i = 0; i < n; i++)         parent[i] = i;     for (int i = 0; i < costs.size(); i++)         v.push_back({ costs[i][2], { costs[i][0], costs[i][1] } });//비용을 기준으로 정렬을 해야하기때문에 첫번째값을 비용으로 넣어줌     sort(v.begin(), v.end());//비용을 기준으로 정렬       return answer; } Colored by Color Scripter

cs

 

모르는점 혹은 궁금한점 혹은 논리적으로 맞지않는것이 있다면 언제든지 댓글을 이용해주시길 바랍니다.