크루스칼로 풀었다.
/**
실수:
disjoint함수의 두 a,b값이 다른 경우 uf[disjoint(a)] = disjoint(b); 최상위 번호를 찾아 넣어줘야하는데...
uf[a] = disjoint(b) 로 넣어주었다.. ㅠㅠ
이렇게 되면 두집합이 합쳐질때 최상위번호가 바뀌는게 아니라.. 중간쯔음에서 바뀌기 때문에... 집합 전체가 합쳐지지 않는다.
오히려 이건 가능하다.
uf[disjoint(a)] = b
b는 최상위가 아니여도... a의 최상위를 b로 바꿔주었기때문에.. disjoint 함수를 부르게되면 최상위 번호로 갱신된다.
**/
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 | #include <string> #include <vector> #include <algorithm> using namespace std; bool cmp(const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; } int uf[100]; int disjoint(int x) { if (uf[x] == x) return x; return uf[x] = disjoint(uf[x]); } int solution(int n, vector<vector<int>> costs) { int answer = 0; for (int i = 0; i < n; i++) { uf[i] = i; } int row = costs.size(); sort(costs.begin(), costs.end(), &cmp); for (int i = 0; i < row; i++) { int a = costs[i][0]; int b = costs[i][1]; int cost = costs[i][2]; if (disjoint(a) != disjoint(b)) { uf[disjoint(a)] = disjoint(b); answer += cost; } else { continue; } } return answer; } | cs |
'알고리즘' 카테고리의 다른 글
| 프로그래머스 (Programmers) 입국심사 (0) | 2021.01.12 |
|---|---|
| 프로그래머스 (Programmers) 가장 먼 노드 (0) | 2021.01.11 |
| 프로그래머스(programmers) N으로 표현 (0) | 2021.01.11 |
| [논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수 (0) | 2020.12.28 |
| Visual Studio Code (VS Code) PS용 환경설정 (1) | 2019.02.07 |
짬뽕얼큰하게
