(C++) - 백준(BOJ) 14621번 : 나만 안되는 연애

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

14621번: 나만 안되는 연애

kruskal 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 학교 번호를 1번부터 부여, 성별을 함께 저장하기 위해 map을 사용합니다. 만든 연결 그래프(트리)의 정보를 저장하기 위한 인접리스트 graph도 필요합니다. 그 외에 간선이 저장된 edges, bfs탐색을 위한 ck배열, parent배열 등이 필요합니다.

 

📔 풀이과정

거리의 총합의 최소이므로 최단거리 문제가 아닌 MST 문제입니다. 

 

 1. 학교별 번호를 부과하고 성별을 map에 저장합니다. 

 

 2. 입력 받은 간선을 거리에 대한 오름차순으로 정렬합니다. 서로 다른 성별의 학교로만 n-1개를 골라 MST를 형성합니다. MST형성시 그 간선의 거리는 ans변수에 더해줍니다. 선택한 edge들은 graph로 따로 인접리스트를 구성합니다.

 

 3. bfs수행 : 모든 정점이 하나의 연결그래프에 포함되어야합니다. 따라서 bfs를 수행했을 때 한번에 모든 정점을 탐방할 수 있어야합니다.

 

📔 정답출력

bfs수행 이후 탐방한 정점의 개수가 n이며 한 번만에 모든 정점을 탐색했을 때 ans를 출력합니다. 아니라면 -1을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, m, parent[1001], ans, edgeCnt,treeNum, vectexNum;
map <int, char> collegeMap;
struct Edge {int u, v, w; };
vector <Edge> edges;
vector <int> graph[1001];
int ck[1001];

bool cmp(Edge &a, Edge &b){
    return a.w < b.w;
}

int find(int x){
    if(x == parent[x]) return x;
    return parent[x] = find(parent[x]);
};

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

void bfs(int i){
    ck[i] = 1;
    queue<int>q;
    q.push(i);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto next : graph[x]){
            if(ck[next]) continue;
            ck[next] = 1;
            q.push(next);
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) parent[i] = i;
    for(int i = 1; i <= n; i++){
        char c;
        cin >> c;
        collegeMap[i] = c;
    }

    for(int i = 1,u,v,w; i <= m; i++){
        cin >> u >> v >> w;
        edges.push_back({u,v,w});
    }

    sort(edges.begin(), edges.end(), cmp);

    for(auto e : edges){
        if(collegeMap[e.u] == collegeMap[e.v]) continue;
        if(edgeCnt == n - 1) break;
        if(find(e.u) != find(e.v)){
            merge(e.u,e.v);
            ans += e.w;
            graph[e.u].push_back(e.v);
            graph[e.v].push_back(e.u);
            edgeCnt++;
        }
    }

    for(int i = 1; i <= n; i++){
        if(ck[i]) continue;
        treeNum++;
        bfs(i);
    }

    for(int i = 1; i <= n; i++)
        if(ck[i]) vectexNum++;

    if(vectexNum == n && treeNum == 1) cout << ans;
    else cout << -1;
}