[BOJ 25984 // C++] Extended Braille

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25984번 문제인 Extended Braille이다.
문제는 아래 링크를 확인하자.

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

 

주어지는 각 점자를 구성하는 점 중 가장 왼쪽에 있는 점과 위쪽에 있는 점의 위치를 찾고 그 두 위치를 기준으로 점들을 모두 평행이동시켜 저장하자. 이렇게 저장하면 두 점자가 같은 것과 두 점자를 이루는 점의 좌표가 일치하는 것은 서로 동치가 된다.

 

이제 점을 모은 벡터를 담는 set을 이용해 문제를 해결할 수 있다. 이 과정에서, 같은 점의 모음이 서로 같게 판정되도록 각 벡터가 담은 점은 정렬해두자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int N, K;
set<vector<pair<int, int>>> st;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		cin >> K;
		int mn1 = 1000000007, mn2 = 1000000007;
		vector<pair<int, int>> tmp;
		while (K--) {
			int x, y; cin >> x >> y;
			mn1 = min(mn1, x), mn2 = min(mn2, y);
			tmp.emplace_back(make_pair(x, y));
		}
		for (auto &p : tmp) {
			p.first -= mn1, p.second -= mn2;
		}
		sort(tmp.begin(), tmp.end());
		st.insert(tmp);
	}

	cout << st.size();
}