(C++) 백준 14621 나만 안되는 연애

문제 및 풀이

https://www.acmicpc.net/problem/14621

최소 스패닝 트리

• 임의의 노드에서부터 시작해서 비용이 적은순으로 정렬된 우선순위 큐를 통해 dfs로 탐색한다.
• 싸이클을 만들지 않기 위해 이미 탐색한 노드는 탐색하지 않는다.
• 문제 조건에 의해 같은 성별의 노드는 탐색하지 않는다는 조건을 추가한다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;

char node[1005];
bool isvisited[1005];
vector<pair<int,int>> edge[1005];
int a,b,c;

int main(){

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>N>>M;

    for(int k=1; k<=N; k++) cin>>node[k];

    for(int i=0; i<M; i++) {
        cin>>a>>b>>c;
        edge[a].emplace_back(c,b);
        edge[b].emplace_back(c,a);
    }


    priority_queue<pair<int, int>> pq;
    int ans=0;
    pq.push({0,1});

    while(!pq.empty()){

        int now = pq.top().second;
        int cost = pq.top().first*(-1);
        pq.pop();

        if(isvisited[now]) continue;
        isvisited[now]=true;
        ans+=cost;

        for(int i=0; i<edge[now].size(); i++){
            int next = edge[now][i].second;
            int nextCost = edge[now][i].first;

            if(node[next]==node[now]) continue;
            pq.push({-nextCost, next});
        }
    }

    for(int i=1; i<=N; i++) if(!isvisited[i]) {cout<<"-1"; return 0 ;}
    cout<<ans;

}