반응형
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42861
문제
풀이, 코드 (크루스칼 알고리즘)
이 문제를 처음에는 어 그냥 최솟값에 대해서 연결만 하면 끝나는거 아니야? 하면서 코드를 일일히 나열했다.
근데 풀다가 생각을 해보니 이럴때 각 노드의 연결 값을 최소화!! 할때 크루스칼 알고리즘을 사용하는것이 기억이 났습니다.
크루스칼 알고리즘, 최소신장트리(MST)에 대한 그림과 함께 쉽게 설명👇👇👇
https://bendeng-life.tistory.com/142
풀이 순서는 이러합니다
1. vector nodes(n,0) 초기화 -> 나중에 부모 노드를 찾기 위해 사용
2. 섬과의 연결되는 다리의 비용을 오름차순으로 정렬
3. 1) 오름차순으로 정렬했으니 사이클을 이제 확인해야 한다.
(연결시 nodes[0] = 1 nodes[1] = 0이 됨)
2) 사이클이 생성되지 않았다면 두 노드를 연결한다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool costCompare(vector<int> a, vector<int> b){
return a[2] < b[2];
}
int getParent(int idx, vector<int> nodes){
if(nodes[idx] == idx)
return idx;
return nodes[idx] = getParent(nodes[idx],nodes);
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
vector<int> nodes(n,0);
sort(costs.begin(),costs.end(),costCompare);
for(int i = 0; i < n;i++){
nodes[i] = i;
}
for(int i = 0; i < costs.size();i++){
int connect = getParent(costs[i][0],nodes); //연결 시작점
int connected = getParent(costs[i][1],nodes); // 연결 받는점 -> 물론 양뱡향인데 표현을 위해
int cost = costs[i][2];
if(connect != connected){
answer+= cost;
nodes[connected] = connect;
}
}
return answer;
}
반응형
'알고리즘 > c++ 프로그래머스' 카테고리의 다른 글
[프로그래머스] 택배상자 c++ (풀이,코드) (0) | 2023.09.08 |
---|---|
[프로그래머스 완주하지 못한 참가자] c++ (풀이,코드) (0) | 2023.07.09 |
[프로그래머스 개인정보 수집기간] c++ (풀이,코드) (0) | 2023.07.05 |
[프로그래머스 신고결과받기] c++ (풀이,코드) (0) | 2023.07.05 |
[프로그래머스 가장 먼 노드] c++ (풀이,코드, bfs) (0) | 2023.07.04 |
댓글