← All Articles

[BAEKJOON] 14621. 나만 안되는 연애

Posted on

문제 :

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

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

  1. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.
  2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.
  3. 시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.

만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다.

image

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


입력 :

입력의 첫째 줄에 학교의 수 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을 출력한다.)



풀이 :

대표적인 MST 유형의 문제인 듯 하다. 간단한 Minimum Spanning Tree 구현 문제에서 조건이 추가된 것으로 치면 여초 대학교와 남초 대학교 사이의 도로로만 이루어져 있기 때문에 양 쪽 끝 노드의 대학교 구분 문자( ‘W’ or ‘M’ ) 가 다른 경로로만 이루어진 최소 스패닝 트리를 구해야한다.

최소 스패닝 트리의 개념만 잘 알고 설계한다면? 그렇게 어렵지 않은 문제인 듯 하다.

오랜만에 MST 문제를 풀면서 복습이 된 것 같다.



코드 :

코드 보기/접기 
#include <iostream>
#include <vector>
#include <utility>
#include <queue>

#define pii pair<int, int>

using namespace std;
vector<char> univvec;
vector<vector<pii>> adj;
int n;

int calculFullPathLength() {
    bool *visit = new bool[n + 1]{false};
    int visitcnt = 0, distsum = 0;
    priority_queue<pii, vector<pii >, greater<>> pq;
    pq.push(pii(0, 1));

    while (!pq.empty()) {
        int curidx = pq.top().second, curdist = pq.top().first;
        pq.pop();
        if (visit[curidx]) continue;
        visitcnt++;
        visit[curidx] = true;
        distsum += curdist;

        if (visitcnt >= n) return distsum;

        int size = adj[curidx].size();
        for (int k = 0; k < size; k++) {
            if (univvec[curidx] == univvec[adj[curidx][k].first]) continue;
            pq.push(pii(adj[curidx][k].second, adj[curidx][k].first));
        }
    }

    return -1;
}

int main() {
    int pathnum, fir, sec, weight;
    cin >> n >> pathnum;

    univvec.resize(n + 1);
    adj.resize(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> univvec[i];

    while (pathnum--) {
        cin >> fir >> sec >> weight;
        adj[fir].emplace_back(sec, weight);
        adj[sec].emplace_back(fir, weight);
    }

    cout << calculFullPathLength() << '\n';
    return 0;
}


AlgorithmalgorithmbaekjoonC++