[Algorithm] [C++] 부채꼴 범위 안의 적 판별하기

해당 문제는 최근 한 기업의 입사 코딩테스트에서 나왔던 문제입니다.

 

유명한 온라인 게임 리그오브레전드의 '애쉬' 챔피언이 스킬을 사용하는 그림이

이 문제의 설명을 돕는 이미지로 출제 되었습니다.

 

게임을 해보지 않은 분들도 위 이미지를 보시면 쉽게 이해가 되실 겁니다.

 

문제 내용을 복원하여 보겠습니다.

(기억에 의존하므로 정확하지 않을 수 있습니다.)

 

문제 :

한 게임의 캐릭터가 스킬을 사용합니다.

해당 캐릭터가 스킬을 사용할 때. 스킬은 부채꼴 범위로 퍼지면서 나갑니다.

해당 부채꼴 범위 안에 적이 있다면, 적은 데미지를 받지만, 범위 밖이라면 데미지를 받지 않습니다.

데미지를 받는 적의 수를 Return하세요.

 

조건1 : 스킬을 사용하는 주체인 게임 캐릭터는 항상 0,0 위치에 있습니다.

조건2 : 적들은 0,0에 있을 수 없으며, 겹쳐있지 않습니다.

조건3 : 캐릭터와 일직선상에 적이 2명 이상 겹쳐있어도, 범위 안에만 들어오면 다 데미지를 받는 것으로 인식합니다.

(이건 잘 기억이 안나는데.. 대충 이런 식이었던것 같습니다. 실제 애쉬 W랑은 다르다는 얘기..)

 

 

주어지는 값 : 

1. 스킬을 사용하기위해 위치해있는 마우스 좌표 int x,y

2. 스킬의 길이(반지름) int r

3. 각도(만약 60도면, 중심선으로부터 시계방향으로 60도, 반시계방향으로 60도.. 따라서 최대 스킬범위는 120도..) int d

4. 적들의 위치 xn, yn이 담긴 int형 2중벡터 vector<vector<int> > target

 

 

해설 :

이 문제는 다음과 같은 3가지 단계로 풀 수 있습니다.

 

1. 일단, 원의 반지름(r)이 주어지므로, (0,0)을 원점으로 하는 원을 그려 이 범위 안에 있는 적들을 모두 파악하고, 밖의 적들은 버립니다.

 

2. (0,0)과 스킬을 사용한 좌표(x,y)까지의 일직선을 그리면, 그것이 부채꼴의 중심선이 됩니다. (벡터 A)

(0,0)과 적의 좌표(xn,yn)까지의 일직선을 그리면, 또 하나의 벡터가 생겨납니다(벡터 B)

구한 2개의 벡터 사이의 [각도]를 [원의 내적]을 구하는 방법을 응용하여 계산합니다.

 

3. 계산한 각도가 주어진 각도(d)보다 작으면, 그 적은 스킬 범위 안에 있는 것입니다. 범위 내에 있는 적들을 판별하는 반복문을 구현합니다.

 

코드 : 

 

우선 적과의 거리가 주어진 반지름(r)보다 적으면, 원 안에 들어오는 것이므로, 거리를 계산하는 함수를 하나 만들어줍니다.

double Distance(double x, double y) { 
	double distance; 
	distance = sqrt(pow(x, 2) + pow(y, 2)); 
	return distance; 
} 

거리 계산에는 학창시절에 배운 피타고라스의 정리를 사용합니다.

sqrt = 제곱근, pow = 제곱

 

거리를 구하였으면, 거리 밖의 있는 적들은 걸러줍니다.

거리 안에 있는 적들은 따로 벡터 안에 담아줍니다.

vector<vector<int> > intarget;

for(int i=0; i<target.size(); i++){
	if(Distance(target[i][0], target[i][1] <=r)
	{
		intarget.push_back(target[i]);
	}
}

여기까지 1단계가 끝납니다..

 

 

담긴 적들로 다시 2단계를 풀어야합니다.

2단계를 다시 설명드리면,

 

(0,0)과 스킬을 사용한 좌표(x,y)까지의 일직선을 그리면, 그것이 부채꼴의 중심선이 됩니다. (벡터 A)

(0,0)과 적의 좌표(xn,yn)까지의 일직선을 그리면, 또 하나의 벡터가 생겨납니다(벡터 B)

구한 2개의 벡터 사이의 [각도]를 [원의 내적]을 구하는 방법을 응용하여 계산합니다.

 

이젠 벡터의 내적을 구하는 공식이 필요합니다. 이것이 왜 필요하냐면,

두 벡터의 내적을 구하는 공식은 

|A|(벡터A의 크기) * |B|(벡터B의 크기) * cosin(각도) 입니다.

 

여기서 앞의 |A|*|B|를 나누어주면 결국 각도만 남게 되기 때문에,

벡터 A와 벡터 B의 각도를 구할 수 있습니다.

 

이 과정을 도와줄 함수를 작성합니다.

벡터의 크기 구하는 공식(증명에 대해선 구글링을...)

double Vector_size(double A1, double A2) 
{ 
	return sqrt(pow(A1, 2) + pow(A2, 2)); 
} 

 

벡터의 내적을 구하는 공식(증명에 대해선 구글링을...)

 

double Inner_func(double x, double y, double x1, double y1) 
{ 
	return (x*x1) + (y*y1); 
} 

이제 계산만 해주면 적과의 각도가 나옵니다..

int nCount = 0;
double u, v, inner, theta;

for(int i=0;i<intarget.size();i++)
{
	// 두 벡터의 크기 u,v 구하기
	u = Vector_size(x,y);
	v = Vector_size(interget[i][0], intarget[i][1]);
    
	// 두 벡터간의 내적 구하기
	inner = Inner_func(x,y,interget[i][0], intarget[i][1]);
	
	// 두 벡터간의 내적에 두 벡터의 크기를 곱한 것을 나누어 두 벡터간의 각도 구하기
	// acos함수는 구글링을..
	theta = acos(inner/(u*v));
    
	// 만약 두 벡터간의 각이 주어진 각보다 작다면, 이는 범위 내의 적으로 판단
	if(theta <=d)
		nCount++;
}

 

마지막으로 nCount를 리턴해주면 이 문제는 해결할 수 있습니다.

 

고등학교 과정 정도의 난이도인듯 합니다.

내적으로 두 벡터간의 각도를 구하는 방법이 바로 떠오르셨다면 금방 푸실 수 있는 문제이지만,

저같은 경우엔 수학의 기초가 탄탄하지 못한 편이기 때문에 이 방법을 바로 떠올리지 못해서

푸는데 한시간 정도 소요되었습니다.