백준 알고리즘 15685_드래곤커브 C,C++

문제

(링크)15685번: 드래곤 커브 (acmicpc.net)

15685번: 드래곤 커브

사고과정

처음에 문제가 조금 헷갈려서 아래에 있는 예시까지 보고 확실하게 이해했다. 먼저 생각한 것은 주어지는 각 드래곤커브마다 정보를 업데이트 해야한다. 이후 격자 안의 점들을 탐색하며 사각형을 찾아야겠다고 생각했다.

그런데 문제는 어떻게 드래곤 커브를 주어진 세대만큼 업데이트 하느냐이다. 먼저 문제에서 주어진 격자는 우리가 흔히 사용하는 좌표평면을 x축 대칭한 모양이다. 즉 문제에서 주어진 '시계방향' 회전은 실제 좌표평면에서의 '반시계 방향'회전이다. 좌표평면에서 원점을 기준으로한 반시계방향으로 90도 회전은    

회전변환 공식

으로 표현할 수 있다. 이 공식을 이용하여 '기준점'과 '현재점'의 차이를 오른쪽 x,y에 대입하면 '새로운점'과 '기준점'의 차이가 나온다. 드래곤 커브의 기준점의 '마지막으로 추가된 점'이므로 현재 갱신된 드래곤커브의 모든점을 회전해서 추가하면 점을 구할 수 있다

 

내코드

#include <vector>
#include <stdio.h>

using namespace std;

typedef struct {
	int generation;
	vector<pair<int, int>> point;
}dragon_curve;

dragon_curve D[20];

int map[101][101] = { 0 };
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
int max_x = 0, max_y = 0;
int rotate[2][2] = { {0,1},{-1,0} };

void update_state(vector<pair<int, int>>& curve, int dir) {
	int x = curve[0].second;
	int y = curve[0].first;

	int Y = y + dy[dir];
	int X = x + dx[dir];
	curve.push_back(make_pair(Y, X));//입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다
	map[Y][X] = 1;
	if (Y > max_y)max_y = Y;
	if (X > max_x)max_x = X;
}

void update_rotation90(vector<pair<int,int>>& curve, int r_count, int generation) {
	if (r_count == generation)return;
	
	int size = curve.size();
	int O_x = curve[size-1].second;
	int O_y = curve[size-1].first;
	
	for (int i = size - 2; i >= 0; i--) {
		int dx = O_x - curve[i].second;		//일반적인 좌표계에서 반시계방향 회전은
		int dy = O_y - curve[i].first;		//반전 좌표계에서 시계방향으로 회전
		int tmp = dx;					
		dx = dy;							
		dy = -tmp;
		int Y = O_y + dy;
		int X = O_x + dx;
		curve.push_back(make_pair(Y, X));	
		map[Y][X] = 1;
		if (Y > max_y)max_y = Y;
		if (X > max_x)max_x = X;
	}
	update_rotation90(curve, r_count + 1, generation);
}



int main() {
	int N,i,j;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		int x, y, dir, gen;
		scanf("%d %d %d %d", &x, &y, &dir, &gen);
		D[i].point.push_back(make_pair(y, x));
		map[y][x] = 1;
		D[i].generation = gen;
		update_state(D[i].point, dir);			//처음 0세대의 드래곤커브를 표시
	}

	for (i = 0; i < N; i++) {			//각 드래곤 커브 업데이트 및 map에 표시
		update_rotation90(D[i].point, 0, D[i].generation);
	}
	
	int answer = 0;
	for (i = 0; i <= max_y; i++) {
		for (j = 0; j <= max_x; j++) {
			if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1]) {
				answer++;
			}
		}
	}

	printf("%d", answer);


	return 0;
}

각 함수의 기능은 위에서 설명한 것처럼 순서대로 드래곤 커브의 다음 지점들을 갱신한다. 

 

피드백

코드를 제출하고 생각해보니깐, 굳이 저렇게 회전변환을 이용안하고 direction을 각 지점에 저장하여 다음 점을 갱신해도 되겠다고 생각했다. 나중에 direction을 이용해 코드를 만들어볼것.