백준 알고리즘 15685

입력 : 드래곤 커브 갯수, 각 드래곤 커브의 시작점과 시작 방향 및 세대

출력 : 네 꼭지점이 모두 드래곤커브인 정사각형의 갯수

 

풀이

1. 한 드래곤 커브에 대한 정보를 입력받으면 바로 드래곤커브를 그린다.

2. 최소 1세대 이상이기 때문에 0세대 드래곤커브를 우선 그린다.

3. 세대만큼 반복문을 사용해 드래곤 커브를 그린다
        - 각 점을 드래곤커브의 마지막 점을 기준으로 시계방향 90도 회전한 지점에 복사한다.
          이를 위한 식은 다음과 같다.
          x = p.x - stdp.x;
          y = p.y - stdp.y;
          return getPoint(stdp.x - y, stdp.y + x);
        - 드래곤 커브는 bool 2차원 배열에 표현한다.

4. 모든 드래곤 커브를 그린 다음 전체 판에서 꼭지점이 모두 드래곤커브인 정사각형의 개수를 찾는다.

 

#include <iostream>
#include <vector>
using namespace std;
struct Point{
	int x;
	int y;
};
int curveList[21][5];
bool board[102][102];
int direction[4][2] = {{1,0}, {0,-1}, {-1,0}, {0,1}};
Point getPoint(int x, int y){
	Point result;
	result.x = x;
	result.y = y;
	
	return result;
}
Point getCurvedPoint(Point p, Point stdp){
	int x, y;
	
	x = p.x - stdp.x;
	y = p.y - stdp.y;
	
	return getPoint(stdp.x - y, stdp.y + x);
}
void makeCurve(int x, int y, int direct, int level){
	vector<Point> points;
	
	points.push_back(getPoint(x, y));
	points.push_back(getPoint(x + direction[direct][0], y + direction[direct][1]));
	
	for(int i=1; i<=level; i++){
		int pointNum = points.size();
		Point stdp = points[pointNum-1];
		
		for(int j=pointNum-2; j>=0; j--){
			Point temp;
			temp = getCurvedPoint(points[j], stdp);
			points.push_back(temp);
		}
	}
	
	for(int i=0; i<points.size(); i++){
		board[points[i].x][points[i].y] = true;
	}
	points.clear();
}
int main() {
	int N;
	
	cin>>N;
	
	for(int i=0; i<N; i++){
		int x, y, d, g;
		cin>>x>>y>>d>>g;
		makeCurve(x, y, d, g);
	}
	
	int n = 0;
	
	for(int i=0; i<100; i++){
		for(int j=0; j<100; j++){
			if(board[i][j] && board[i+1][j] && board[i][j+1] && board[i+1][j+1]){
				n++;
			}
		}
	}
	cout<<n;
	return 0;
}