[백준 / BOJ] C++ 1414 불우이웃돕기

1414번: 불우이웃돕기

 

문제

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

1414번: 불우이웃돕기

 

 

풀이

최소 스패닝 트리(MST) 변형문제 중 하나로 간선의 가중치가 알파벳으로 입력된다. 문제 조건에 따라 ascii 코드를 기준으로 연산하여 간선을 저장한다. 기부할 수 있는 랜선의 길이는 최소 스패닝 트리의 가중치를 제외한 모든 가중치의 합이므로 간선을 저장할 때마다 cost에 가중치를 더해주고 최소 스패닝 트리의 컴포넌트를 연결할 때마다 간선의 가중치만큼 cost에서 빼주는 방식으로 구현했다.

 

그리고 모든 컴퓨터가 연결되어 있는지 판단은 아래 링크 문제와 같은 방식으로, 모든 정점에 대해 find 함수를 수행해 루트를 가리키도록 한 다음, 합을 정점의 수와 비교해 줬다. 이유는 모든 컴포넌트가 연결되어 있다면 모두 1을 가리키고 있기 때문이다.

https://khyunx.tistory.com/212

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

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int N, cost = 0;
vector<pair<int, pair<int, int>>> edge;
vector<int> p;

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

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[y] = x;
  else
    p[x] = y;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  p.resize(N + 1);
  iota(p.begin(), p.end(), 0);
  for (int i = 1; i <= N; i++) {
    string s;
    cin >> s;
    for (int j = 1; j <= N; j++)
   	  // 문자가 '0'이 아닐 때
      if (s[j - 1] != '0') {
        if (s[j - 1] >= 'a') { // 문자가 'a'-'z' 사이인 경우
          edge.push_back({s[j - 1] - 'a' + 1, {i, j}});
          cost += s[j - 1] - 'a' + 1;
        } else { // 문자가 'A'-'Z' 사이인 경우
          edge.push_back({s[j - 1] - 'A' + 27, {i, j}});
          cost += s[j - 1] - 'A' + 27;
        }
      }
  }
  // 크루스칼 알고리즘
  sort(edge.begin(), edge.end());
  for (auto [weight, path] : edge)
    if (find(path.first) != find(path.second)) {
      // 전체 가중치에서 MST의 가중치 차감
      cost -= weight;
      merge(path.first, path.second);
    }
  // 배열의 원소가 모두 루트를 가리키도록
  for (int i = 1; i <= N; i++)
    find(i);
  // 모든 원소의 루트가 1인 경우
  // 즉, 배열의 원소의 합이 정점의 수와 같을 때
  if (accumulate(p.begin(), p.end(), 0) != N)
    cout << -1;
  else
    cout << cost;
  return 0;
}