프로그래머스 - 전력망을 둘로 나누기 (c++)

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

완전탐색 카테고리에 있는 레벨2 문제

입력으로는 하나의 네트워크로 뭉쳐있는 트리가 주어지고 전선을 한개씩 자르면서 네트워크가 두 개로 나누어지고 네트워크간 송전탑 개수의 차이가 최소로 하는 값을 구하면 된다.

결론적으로 나는 완전탐색 + 크루스칼 을 사용해서 풀었다.

전선을 하나씩 자르면서 생기는 네트워크가 몇개인지 파악하고 각 송전탑이 어떤 네트워크에 속하고 있는지 알기 위해 크루스칼을 사용했다.

또한, 두 개의 네트워크가 생겼을 때 각 네트워크에는 몇개의 송전탑이 존재하는지 확인하기 위해 HashMap 자료구조를 사용했다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int root[101];

int find_root(int idx) {
  if (root[idx] == idx)
    return idx;
  return root[idx] = find_root(root[idx]);
}

int solution(int n, vector<vector<int>> wires) {
  int answer = INT_MAX;

  for (int i = 0; i < wires.size(); i++) {
    for (int t = 1; t <= n; t++)
      root[t] = t;
    for (int j = 0; j < wires.size(); j++) {
      if (i == j)
        continue;
      int x = find_root(wires[j][0]);
      int y = find_root(wires[j][1]);
      if (x != y) {
        root[y] = x;
      }
    }
    unordered_map<int, int> M;
    for (int t = 1; t <= n; t++) {
      int root = find_root(t);
      if (M.find(root) == M.end()) {
        M[root] = 1;
      } else {
        M[root] += 1;
      }
    }
    int diff = 0;
    int sign = 1;
    if (M.size() == 2) {
      for (auto a : M) {
        diff += a.second * sign;
        sign = -1;
      }
      answer = min(answer, abs(diff));
    }
  }
  if (answer == INT_MAX)
    answer = 0;
  return answer;
}