[백준 / BOJ] C++ 17430 가로등

17430번: 가로등

 

문제

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

17430번: 가로등

 

 

풀이

두 전봇대의 x좌표가 같은 경우, y좌표를 바꾸어도 반드시 균형 잡힐 수밖에 없다.

두 전봇대의 x좌표가 다른 경우, x좌표에 대한 y좌표의 집합이 같은 경우에만 균형 잡혀있다고 볼 수 있다.

따라서 집합 비교를 위해 map을 사용해 key를 x좌표로, value를 y좌표의 집합으로 사용했다. (벡터의 배열로 만들었어도 괜찮았을 것 같다.) 각 집합을 오름차순 정렬하여 비교에 용이하도록 했다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, flag = 0;
    cin >> n;
    map<int, vector<int>> m;
    for (int i = 0; i < n; i++) {
      int x, y;
      cin >> x >> y;
      m[x].push_back(y);
    }
    for (auto &i : m)
      sort(i.second.begin(), i.second.end());
    for (auto i : m) {
      if (flag)
        break;
      for (auto j : m) {
        if (i.first == j.first)
          continue;
        if (i.second != j.second) {
          flag = 1;
          break;
        }
      }
    }
    cout << (flag ? "NOT BALANCED\n" : "BALANCED\n");
  }
  return 0;
}