[프로그래머스]level-3 섬 연결하기(크루스칼 알고리즘)
https://programmers.co.kr/learn/courses/30/lessons/42861
크루스칼 알고리즘을 통해 각 섬을 연결하는 최소 비용, MST(최소 비용 신장 트리)를 얻는 것이 목표인 문제이다.
신장 트리(Spanning Tree)는 기존 그래프의 모든 노드를 포함하지만 싸이클이 존재하지 않는 그래프 트리를 말합니다.
방법
- 각 간선을 오름차순으로 정렬 (가중치)
- 간선의 양쪽끝이 싸이클을 이루지 않으면 (dfs로 한쪽에서 한쪽으로 도착하지 않으면) 연결한다!(사용)
- 싸이클을 이루는 간선은 채택하지 않는다!
내 코드
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> graph[101];
bool check[101] = {false,};
bool b = false;
int to;
bool cmp(vector<int> a, vector<int> b) {
return a[2] < b[2];
}
void dfs (int start) {
check[start] = true;
for (int i = 0; i < graph[start].size(); i++) {
if (to == graph[start][i]) {
b = true;
return;
}
if (!check[graph[start][i]]) dfs(graph[start][i]);
}
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
sort(costs.begin(), costs.end(), cmp);
for (int i = 0; i < costs.size(); i++) {
int start = costs[i][0];
to = costs[i][1];
memset(check, false, sizeof(check));
dfs(start);
if (!b) {
graph[start].push_back(to);
graph[to].push_back(start);
answer += costs[i][2];
} else {
b = false;
}
}
return answer;
}
- b 라는 boolean 전역 변수는 간선이 싸이클을 이루는지 아닌지를 가리고
- b 를 체크해서 그래프를 형성하고 가중치를 정립한다.
Author And Source
이 문제에 관하여([프로그래머스]level-3 섬 연결하기(크루스칼 알고리즘)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@isntkyu/프로그래머스level-3-섬-연결하기크루스칼-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)