[해커랭크(HackerRank)] - Queen's Attack II

[문제 링크]

https://www.hackerrank.com/challenges/queens-attack-2/problem

 

[함수부 구현(C++)]

int calc_delta(int r1, int c1, int r2, int c2)
{
	int delta_r;
	int delta_c;

	delta_r = r2 - r1;
	delta_c = c2 - c1;

	if (delta_r == 0 || delta_c == 0) {
		return 0;
	}
	
	if (abs(delta_r) - abs(delta_c) == 0) {
		return 1;
	}

	return 2;
}

// Complete the queensAttack function below.
int queensAttack(int n, int k, int r_q, int c_q, vector<vector<int>> obstacles) {

	int dr[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
	int dc[] = { 0, 1, 1, 1, 0 ,-1, -1, -1 };

	int attack_count = 0;

	vector<pair<int,int>> n_obstacles;

	/* filtering obstacles */
	for (int i = 0; i < k; i++) {
		int delta = calc_delta(r_q, c_q, obstacles[i][0], obstacles[i][1]);
		if (delta == 0 || delta == 1) {
			n_obstacles.push_back(make_pair(obstacles[i][0], obstacles[i][1]));
		}
	}

	for (int i = 0; i < 8; i++) {

		int qr = r_q;
		int qc = c_q;

		while (1) {
			int blocking = 0;
			int find_obs = 0;

			qr = qr + dr[i];
			qc = qc + dc[i];


			if (qr < 1 || qr > n || qc < 1 || qc > n) {
				blocking = 1;
			}

			if (blocking == 1) {
				break;
			}

			vector<pair<int, int>>::iterator it;
			for (it = n_obstacles.begin(); it != n_obstacles.end(); it++) {
				if (qr == it->first && qc == it->second) {
					find_obs = 1;
					break;
				}
			}

			if (find_obs == 1) {
				break;
			}

			attack_count++;
		}
	}

	return attack_count;
}

[내용]

queen의 path를 그릴때 n*n좌표 범위를 벗어나지 않게 blocking 처리해주고

obstacle를 만날 때 해당 방향 path는 그만그리도록 해야하는데

 

문제는 입력받을 수 있는 obstacle의 개수가 너무 많아서 path한칸 확인할때마다

입력받은 모든 obstacle들을 검사하기에는 좌표 하나당 소비하는 시간이 너무 오래걸림...

 

obstacle의 개수가 10만개나 올 수 있는데

사실 Queen이 만나는 obstacle는 최대 방향당 1개, 다시말해 8개인점을 고려하여
시간절약이 필요한 문제임을 예측했다

 

나는 10만개의 obstacle를 방향당 queen의 최소거리에 있는 8개만 추려내는 방법은 못찾았고

queen위 좌표와 obstacle[i]의 좌표를 이용하여 기울기가 0, 1, -1인 obstacle들만

별도로 추려내어 새로 정의한 vector<pair<int, int>> 에 담았다

 

이제 queen의 path를 그릴때는 기울기 계산하여 추려낸 n_obstacle vector를 loop태워서 그려내면 성공