[백준/C++] 14621번. 나만 안되는 연애

[백준/C++] 14621번. 나만 안되는 연애

1. 문제

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

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

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

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

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

2. 입력

입력의 첫째 줄에 학교의 수 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)

3. 출력

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

4. 풀이

• 최소 신장 트리 문제
• n개의 학교의 parent 배열을 초기화 하면서 여초학교인지 남초학교인지 입력 받아 boolean타입의 gender 배열에 저장한다.
• m개의 도로 정보를 입력 받는다.
• 도로 정보를 오름차순으로 정렬한다.
• 도로 정보를 꺼내서 사이클이 생기지 않으면서 서로 다른 성비를 가진학교이면 도로 비용을 더해주고 합집합해준다.
  조건문을 같지 않다고 해도 되는데 boolean 배열이기도 하고 XOR 쓰고 싶어서 썼다.
• 모든 작업이 끝난 후 각 학교의 부모가 같은지 확인한다.
• 부모가 다른 학교가 있다면 연결되지 않은 학교기 때문에 -1을 출력해야 한다.

5. 처음 코드와 달라진 점

• 모든 학교를 연결하는 경로가 있는지 확인해주지 않아서 수정했다.

6. 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int parent[1001];
bool gender[1001];
vector<pair<int, pair<int, int> > > v;

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

void unionParent(int a, int b) {
  a = findParent(a);
  b = findParent(b);

  if (a < b) parent[b] = a;
  else parent[a] = b;
}

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

  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    char gen;
    cin >> gen;

    gender[i] = gen =='M' ? true : false;
    parent[i] = i;
  }

  for (int i = 0; i < m; i++) {
    int a, b, cost;
    cin >> a >> b >> cost;

    v.push_back(make_pair(cost, make_pair(a, b)));
  }

  sort(v.begin(), v.end());

  int totalCost = 0;
  for (int i = 0; i < m; i++) {
    int a = v[i].second.first;
    int b = v[i].second.second;
    int cost = v[i].first;

    if ((findParent(a) != findParent(b)) && (gender[a] ^ gender[b])) {
      totalCost += cost;
      unionParent(a, b);
    }
  }

  bool isConnected = true;
  for (int i = 1; i < n; i++) {
    if (findParent(i) != findParent(i+1)) {
      isConnected = false;
      break;
    }
  }
  
  if (isConnected) cout << totalCost;
  else cout<< -1;
}```