나만 안되는 연애

알고리즘 구분 : 그래프 이론, 최소 스패닝 트리

문제

깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.

이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.

사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.
사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.
시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.
만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다.

이때, 주어지는 거리 데이터를 이용하여 사심 경로의 길이를 구해보자.

입력
입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000)

둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다.

다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000)

출력
깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.)

예제 입력 1
5 7
M W W W M
1 2 12
1 3 10
4 2 5
5 2 5
2 5 10
3 4 3
5 4 7
예제 출력 1
34

문제 풀이

MST를 풀 때 가장 일반적으로 쓰고 있는 크루스칼 알고리즘을 이용하여 풀었다.
오랜만에 MST 유형의 문제를 풀려고 하다보니, 크루스칼 알고리즘을 어떻게 구현했었는지에 대한 기억이 가물가물하여 시간이 조금 걸렸던 문제였다.

일반적인 크루스칼 알고리즘 구현 방식을 그대로 구현한 이후에, 남초 학교와 여초 학교에 대한 정보 배열을 활용한 조건문 하나만 더 활용하여 union 연산을 하도록 구현하면 되는 문제이다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n, m;
int parent[1001];
bool col[1001];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
int findParent(int parent[], int x);
void unionParent(int parent[], int a, int b);
void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

        if(input == 'M') {
            col[i] = true;
        }
        else {
            col[i] = false;
        }
    }
    for(int i = 0; i < m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        pq.push({d, {u ,v}});
    }

    solve();

    return 0;
}

int findParent(int parent[], int x) {
    if(parent[x] != x) {
        return parent[x] = findParent(parent, parent[x]);
    }

    return parent[x];
}

void unionParent(int parent[], int a, int b) {
    int pa = findParent(parent, a);
    int pb = findParent(parent, b);

    if(pa < pb) {
        parent[pa] = pb;
    }
    else {
        parent[pb] = pa;
    }
}

void solve() {
    int cnt = 0;
    int result = 0;

    while(!pq.empty()) {
        int dist = pq.top().first;
        int a = pq.top().second.first;
        int b = pq.top().second.second;
        
        pq.pop();

        if(findParent(parent, a) != findParent(parent, b) && col[a] != col[b]) {
            unionParent(parent, a, b);
            result += dist;
            cnt++;
        }
    }

    if(cnt == n - 1) {
        cout << result << endl;
    }
    else {
        cout << -1 << endl;
    }

}

• 문제 출처 : https://www.acmicpc.net/problem/14621
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.