https://school.programmers.co.kr/learn/courses/30/lessons/42861
문제 해결 과정
착안
문제에서 요구하는 결과값이 최소 신장 트리(minimum spanning tree)의 간선의 가중치의 총합이므로, 최소 신장 트리 알고리즘을 활용하여 문제를 해결하고자 하였다.
구현
간선 데이터가 주어지므로, 유니온-파인드(union-find) 연산을 구현한 다음 크루스칼 알고리즘(Kruskal's algorithm)을 통해 최소 신장 트리를 만들어 가중치의 총합을 구하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <vector>
#include <algorithm>
using namespace std;
int Parent[100];
int Find(int a)
{
int temp = a;
while (a != Parent[a])
a = Parent[a];
return Parent[temp] = a;
}
void Union(int a, int b)
{
if (Find(a) != Find(b))
Parent[Parent[b]] = a;
}
int solution(int n, vector<vector<int>> costs)
{
for (int i = 0; i < n; i++)
Parent[i] = i;
sort(costs.begin(),
costs.end(),
[](const vector<int>& a, const vector<int>& b)
{
return a[2] < b[2];
});
int answer = 0;
for (vector<int> cost : costs)
{
if (Find(cost[0]) != Find(cost[1]))
{
Union(cost[0], cost[1]);
answer += cost[2];
}
}
return answer;
}
실행 결과
'C++ 코딩 문제 풀이 > 프로그래머스' 카테고리의 다른 글
[Programmers] 혼자 놀기의 달인 (0) | 2023.12.14 |
---|---|
[Programmers] N-Queen (0) | 2023.12.12 |
[Programmers] 마법의 엘리베이터 (1) | 2023.12.08 |
[Programmers] 귤 고르기 (0) | 2023.12.06 |
[Programmers] 카펫 (2) | 2023.12.05 |
댓글