[프로그래머스] 섬 연결하기 - 탐욕법/C++

About this offer

문제 링크 섬 연결하기 코드 #include <string> #include <vector> #include <algorithm> using namespace std; int parent[100]; int findParent(int a) { if (parent[a] == a) { return a; } return parent[a] = findParent(parent[a]); // 최적화 } void unionParent(int a, int b) { int pa = findParent(a); int pb = findParent(b); if (pa != pb) { if (pa < pb) { parent[pb] = pa; } else { parent[pa] = pb; } } } bool cmp(const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; } int solution(int n, vector<vector<int>> costs) { int answer = 0; // 최소 신장 트리(MST) -> 크루스칼 알고리즘 사용 // 유니온 사용: findParent(), unionParent() // 1. 간선 가중치를 오름차순으로 정렬 // 2. 크루스칼 알고리즘: 간선을 하나 꺼내서 노드들을 유니온 sort(costs.begin(), costs.end(), cmp); for (int i = 0; i < n; i++) { // 부모 테이블 초기화 parent[i] = i; } int cnt = 0; // 현재 사용한 간선 개수 for (const auto& edge : costs) { int u = edge[0]; int v = edge[1]; int w = edge[2]; if (findParent(u) != findParent(v)) { unionParent(u, v); answer += w; cnt++; } if (cnt == n - 1) { break; } } return answer; } 회고 findParent() 에서 return parent[a] = findParent(parent[a]) 로 parent[a] 를 바로 갱신하여 최적화시킬 수 있다. unionParent() 에서 a, b 자체가 아니라 그 부모를 갱신해야 한다. 한 그룹의 대장을 바꿔야 제대로 합쳐지기 때문이다. 예전에는 우선순위 큐로 정렬 효과를 누렸는데, 이번에는 벡터를 가중치 기준으로 오름차순 정렬했다. cmp 의 매개변수를 벡터로 설정하고 특정 원소끼리 비교할 수 있는 것도 처음 알았다. cnt 를 사용하여 사용한 간선 수가 n-1 이 되면 멈추도록 했는데, 최적화 코드이기 때문에 이 문제에선 없어도 된다. 하지만 혹시 몰라 넣었다.

Offer details

Provider

velog

Source

velog-rss

Score

54.38

Confidence

49%