[Hackerrank][C++] Queen's Attack II

문제 링크: https://www.hackerrank.com/challenges/queens-attack-2/problem

 

퀸의 공격범위를 찾는 문제인데요, cursor를 이용해 8방향으로 쭉 진행하다가 장애물을 만나면 멈추고 그 때 까지 방문한 칸 수를 더해서 출력하면 됩니다.

유의해야 하는 점이, 체스판의 가로세로 길이가 최대 10만입니다. bool obstacle[10만][10만]; 이런식으로는 메모리가 부족해 불가능하겠죠.

그렇다고 vector<pair<int, int>> obstacle; 이런식으로 배열을 만들고 한 칸 이동할 때마다 현재 좌표와 k개의 장애물의 좌표를 전부 비교하면 TLE가 나올겁니다.

 

그럼 어떻게 장애물 체크를 해야 할까요? 답은 이진탐색입니다.

장애물을 어딘가에 다 넣어놓고 정렬한 다음, 이진탐색으로 찾으면 k가 10만이라고 했을 때 \(log_2{10^5} = 16.6 \dots \)이기 때문에 시간 내에 풀 수 있습니다.

 

장애물을 정렬하는 방법은 여러가지가 있겠는데 가장 간단한 방법은 장애물의 좌표를 string으로 바꾸고 set에다 넣는 겁니다. 좌표를 string으로 바꿀 때 예를 들어 y=1, x=2라고 하면 "1;2" 이런식으로 나타낼 수 있습니다. std::set은 보통 red-black tree로 구현돼있고 find 시간이 O(log n)으로 보장되어 있습니다.

주의할 점은 좌표를 string으로 만들 때 y와 x를 그냥 붙여버리면 중복되는 경우가 발생하니 적절한 delimiter를 넣어줘야 합니다. (ex. "1111" -> y=11, x=11 or y=1, x=111 or y=111, x=1)

#pragma GCC optimize ("Ofast")

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


const int DIR[][2] = { {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1} };
set<string> obstacle;

bool in_range(const int& y, const int& x, const int& n) {
	return y >= 0 && y < n && x >= 0 && x < n;
}

string pt_to_str(const int& r, const int& c) {
	return to_string(r) + "," + to_string(c);
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n, k;
	cin >> n >> k;

	int rq, cq;
	cin >> rq >> cq;
	--rq, --cq;

	while (k--) {
		int r, c;
		cin >> r >> c;
		--r, --c;
		obstacle.insert(pt_to_str(r, c));
	}

	int counter = 0;
	for (const auto& d : DIR) {
		const auto& dy = d[0], & dx = d[1];
		auto y = rq + dy, x = cq + dx;

		while (in_range(y, x, n) && obstacle.find(pt_to_str(y, x))==obstacle.end()) {
			y += dy, x += dx;
			++counter;
		}
	}
	cout << counter << '\n';

	
	return 0;
}

참고로 이 코드랑 문제에 있는 좌표계가 좀 다른데 (0부터 시작, 상하반전 등) 어짜피 범위만 세는 거니까 상관없습니다