[백준 25308] 방사형 그래프 - 힌트에 맞는 풀이

백준 문제 방사형 그래프에 대한 풀이입니다.

기하 관련 문제인 관계로 기하 관련 알고리즘을 몰라 관련 지식만 공부하고 풀이 알고리즘을 디자인하였습니다. 어차피 문제 풀이도 공부하고 브루트포스로 할 경우 시간이 너무 걸릴거 같아 괜한 시간 버리기 싫어 그냥 풀이를 참조하기로 하였습니다. 그래서 검색해서 아래와 같은 풀이를 보았습니다.

[백준 25308] 방사형 그래프

이 풀이를 보고 결국 이 문제는 브루트포스로 하여도 된다는 것을 깨달았습니다. 이 분의 풀이는 굉장히 좋은 발상으로 푼 거 같았습니다. 하지만 이 분의 방법은 백준에 있는 힌트인 "CCW 문제와 어떤 알고리즘을 조합해야 이 문제를 풀 수 있을까요?"하고는 맞지는 않는거 같았습니다. 개인적으로는 이 분이 설명하신 알고리즘으로 모든 볼록다각형을 구하는 것이 가능할까라는 의문이 들기 시작했습니다. 문제 풀이에 대한 발상과 시간 복잡도에서는 우수했지만 개인적으로 기본적으로 모든 볼록 다각형에 적용가능한 알고리즘으로 풀고 싶다는 생각이 들어 처음 설계한 알고리즘으로 문제를 풀었습니다.

풀이를 하기 전에 기본적으로 알고 있어야 하는 지식은 아래와 같습니다.

[알고리즘] CCW(Counter Clock Wise)

3개의 점이 있을 때 어떤 방향을 이루고 있는지를 판단하는 알고리즘으로 2차원 벡터 외적을 응용합니다. 해당 알고리즘으로 아래의 백준 문제를 풀 수 있으며 이 문제를 풀기전에 해당 알고리즘을 공부하고 아래의 백준 문제를 풀어 보는 것이 좋습니다. 

[백준 11758] CCW

도형이 오목 다각형인지 알아보기 - Concave 판단

다각형이 볼록 다각형인지를 판별하는 알고리즘입니다. 볼록 다각형인지 판단하기 위하여 위에 설명한 CCW 알고리즘을 응용합니다. 간단히 이야기 하자면 모든 좌표들이 한방향으로 시계방향이나 반시계방향을 이루는 것으로 다각형이 볼록한지 판단합니다. 여기서 말하는 알고리즘을 구현하기 위하여 점을 3개씩 나누어 CCW을 알고리즘을 적용해 볼 수 있습니다. 즉 여기에 나온 알고리즘을 적용하면 "CCW 문제와 어떤 알고리즘을 조합해야 이 문제를 풀 수 있을까요?"라는 힌트에 맞는 풀이를 만들 수 있습니다.

그럼 풀이 소스를 보겠습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
	double x;
	double y;
};

vector<int> vec;
	
const double PI = 3.1415926;
vector<int> order = { 0, 1, 2, 3, 4, 5, 6, 7 };

const int sz = 8;
Point pt[sz];

inline double rad(double angle)
{
	return angle * PI / 180;
}

int main(int argc, char* argv[])
{
	for(int i=0;i<8;i++)
	{
		int val;
		scanf("%d", &val);
		vec.push_back(val);
	}
	
	sort(order.begin(), order.end());
	
	int ans = 0;
	do {
		for (int i=0;i<8;i++) {
			double x = cos(rad(45*i)) * vec[order[i]];
			double y = sin(rad(45*i)) * vec[order[i]];
			pt[i] = {x, y};
			//printf("%lf %lf\n", x, y);
		}

		bool check = true;
		for (int i=0;i<8;i++) {
			double cp = (pt[(i+1) % 8].x - pt[i].x) * (pt[(i+2) % 8].y - pt[i].y) - (pt[(i+2) % 8].x - pt[i].x) * (pt[(i+1) % 8].y - pt[i].y);
			//printf("%lf\n", cp);
			if (cp < 0.0) 
			{
				check = false;
				break;
			}
		}
		if (check) ans++;
	} while(next_permutation(order.begin(), order.end()));

	printf("%d", ans);
	
	return 0;
}

 

1. 브루트포스 방법을 사용합니다.
모든 능력치를 8곳 모두에서 테스트해보기 때문에 순열을 사용합니다. sort, next_permutation이 순열을 사용하는 코드 입니다. 여기서 order를 사용하는 이유는 같은 숫자을 사용하는 경우 순열로 구분되어 나오지 않기 때문에 모든 곳에서 사용하기 위해서 별도로 배열을 만들어 사용합니다. 예로 입력 1이 8개인 예와 같은 경우 next_permutation에서 케이스가 하나 밖에 나오지 않습니다. 중복된 순열 값과 같은 경우는 나오지 않습니다. 하지만 0~7을 이용한 배열을 이용한 순열과 같은 경우 8!의 경우의 수가 나옵니다. order[i]는 순열 계산으로 나온 수의 인덱스 값을 의미합니다.

2. cos, sin함수를 이용하여 능력치의 실제 2차원 좌표값을 계산합니다.
cos과 sin함수는 라디안 값을 받지만 문제처럼 45도를 이용한 각도 표현을 이용하기 때문에 각도를 라디안으로 변환하여 사용합니다. 능력치가 특정 각도에 표시된다고 할 때 x 값은 cos을 이용하여, y 값은 sin을 이용하여 구할 수 있습니다. 이 부분이 이해가 안가신다면 아날로그 시계 그리는 예제를 찾아보신다면 도움이 되실 수 있습니다.

3. cp는 cross product의 약자로 CCW 알고리즘으로 3개 좌표에 대하여 어떤 방향으로 그려지는 지를 체크합니다.
이 풀이의 핵심적인 부분으로 문제는 각도를 그리는 방향으로(반시계 방향으로) 좌표를 넣은 관계로 CCW 계산에서 시계 방향이 나오면 (cp < 0.0) 다각형에 오목한 부분이 있다는 것을 의미하게 됩니다. 위에서 설명한 대로 볼록 다각형은 시계 방향이나 반시계 방향 이 둘 중의 한방향으로만 좌표가 있어야 합니다. 시계 방향의 결과가 없으면 볼록 다각형으로 판단합니다. 3점에서의 시계 방향이나 반시계 방향 혹은 일직선에서의 값은 CCW알고리즘을 참조하시면 됩니다.