https://programmers.co.kr/learn/courses/30/lessons/42861
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
bool compare(vector<int> a,vector<int> b){ return a[2]>b[2]; }
bool bfs( vector<vector<int>> graph){
queue<pair<int,int>> q;
q.push({0,0});
while(!q.empty()){
int y=q.front().first;
int x=q.front().second;
q.pop();
for(int i=0;i<graph.size();i++){
if(graph[i][x]==1){
graph[i][x]=2;
q.push({i,x});
}
if(graph[y][i]==1){
graph[y][i]=2;
q.push({y,i});
}
}
}
for(int i=0;i<graph.size();i++){
if(graph[i][i]==1) return false;
}
return true;
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
vector<vector<int>> graph(n,vector<int>(n,0));
for(int i=0;i<costs.size();i++){
graph[costs[i][0]][costs[i][1]]=1;
graph[costs[i][1]][costs[i][0]]=1;
answer+=costs[i][2];
}
for(int i=0;i<n;i++){
graph[i][i]=1;
}
sort(costs.begin(),costs.end(),compare);
for(auto i:costs){
graph[i[0]][i[1]]=0;
graph[i[1]][i[0]]=0;
if(bfs(graph)) answer-=i[2];
else{
graph[i[0]][i[1]]=1;
graph[i[1]][i[0]]=1;
}
}
return answer;
}
네트워크 문제와 살짝 비슷해 보이기도 합니다. 섬 개수를 알려주고 섬들을 연결하는 비용을 알려줬을 때 모든 섬을 연결하는 최소 비용을 구하는 문제입니다.
제가 세운 로직은 모든 섬을 연결한 뒤에 비용이 큰 순서대로 하나씩 지워가면서 만약에 지워도 섬이 연결됬다면 지우고 연결이 안된다면 원상복구하는 식으로 값을 구했습니다
코드를 보면 일단 graph에 모든 간선을 연결하면서 비용을 다 더해줍니다.
비용을 기준으로 내림차순으로 간선을 정렬합니다 그 뒤에는 bfs를 활용해서 모든 섬이 연결되있는지를 판단했습니다.