[G5] 백준 5588번 별자리 찾기 C++ 브루트포스 알고리즘, 해시 집합, unordered_set

리뷰

 

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

X, Y좌표를 Key로 하는 해시 집합을 사용해 풀이한 문제

 

 

전역 변수

• X : x좌표와 y좌표를 구분하기 위해 임의로 곱할 값을 정의할 상수 변수
• n : 좌표상의 별의 개수를 저장할 변수
• m : 별자리에 속하는 별의 개수를 저장할 변수
• tx, ty : 별자리 중 기준이 될 별의 x, y좌표를 저장할 변수
• stars : 별의 좌표를 저장할 해시셋

 

함수

없음

 

 

문제풀이

1. m, tx, ty값을 입력 받고, ll타입 벡터 pos를 초기화한다.
2. 초기에 입력 받은 한개의 별을 제외한 별자리의 나머지 m-1개의 별의 위치를 입력 받아 pos에 저장한다.
3. n값을 입력 받고, 모든 별의 위치를 입력받아 stars에 추가한다. 이때 x좌표엔 X를 곱하고 y좌표는 그냥 더한 값이다.
4. stars를 순회하며 변수 x를 star/X, y를 star%X로 저장하고, 변수 diff_x를 tx-x, diff_y를 ty-y로 저장한다.
5. 변수 flag를 true로 초기화하고, pos를 순회한다.
6. 변수 cx를 p/X, cy를 p%X로 초기화 하고, nx를 cx-diff_x, ny를 cy-diff_y로 저장한다.
7. nx, ny가 둘 중 하나라도 0보다 작거나 stars에 X*nx+ny가 존재하지 않는다면 flag를 false로 변경하고 break처리한다.
8. pos를 모두 순회했어도 flag가 true인 경우가 있다면 -diff_x, -diff_y를 공백을 기준으로 출력하고 조기 종료한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. (1 ≤ m ≤ 200, 1 ≤ n ≤ 1000)이므로 브루트포스 알고리즘을 수행해도 시간 복잡도가 충분하다.
2. 별의 x 좌표와 y좌표는 0 이상, 1000000 이하이다. 따라서 X를 100만보다 큰 값으로 해주면 된다.
3. 마찬가지로 좌표가 음수인 별은 없으므로 탐색 중 nx, ny가 0보다 작을 경우 더 이상 탐색할 필요가 없다.
4. pos에 있는 모든 별을 만족하는 기준점을 찾은 경우 더 이상 탐색하지 않고 조기종료 처리해도 된다.

 

정답 코드

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;
using ll = long long;

const ll X = 1e7;
int n, m, tx, ty;
unordered_set<ll> stars;

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

	cin >> m >> tx >> ty;
	vector<ll> pos;
	for (int i = 0; i < m - 1; ++i) {
		int x, y; cin >> x >> y;
		pos.push_back(X * x + y);
	}

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, y; cin >> x >> y;
		stars.insert(X * x + y);
	}

	for (ll star : stars) {
		int x = star / X, y = star % X;
		int diff_x = tx - x, diff_y = ty - y;
		bool flag = true;
		//cout << "===========================\n";
		//cout << x << " " << y << " " << diff_x << " " << diff_y << "\n";

		for (ll p : pos) {
			int cx = p / X, cy = p % X;
			int nx = cx - diff_x, ny = cy - diff_y;
			//cout << cx << " " << cy << " " << nx << " " << ny << "\n";
			if (nx < 0 || ny < 0 || !stars.count(X * nx + ny)) {
				flag = false;
				break;
			}
		}

		if (flag) {
			cout << -diff_x << " " << -diff_y;
			return 0;
		}
	}
}