백준 15685번 - 드래곤 커브

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

처음엔 도통 어떻게 풀어야 하는지 감이 오질 않았다.

고민하던 중 힌트를 얻으려고 검색을 했는데, 단순히 손으로 모양을 그리기만 했지 뻗어나가는 방향의 규칙성을 생각하지 못했다.

 

*이번 세대에서의 curve는 저번 세대까지의 curve 방향 역순과 관련이 있다*

 

#include<iostream>
#include<vector>

using namespace std;

//2차원 좌표평면을 벡터로 만들고, 모든 공간을 0으로 초기화한다.
//드래곤 커브의 시작점을 기준으로, 드래곤 커브를 따라 위에서 만돈 좌표평면의 값을 1로 바꿔준다.
//드래곤 커브의 생성이 끝나면, 사각형을 세는 함수를 사용해 좌상단 끝점을 시작으로 우하단 끝점까지 (x,y)(x+1,y)(x+1, y+1)(x, y+1)이 모두 1인 것이 몇 개나 있는지 카운트한다.

/*
d 값이 의미하는 바

0: x좌표가 증가하는 방향 (→)
1: y좌표가 감소하는 방향 (↑)
2: x좌표가 감소하는 방향 (←)
3: y좌표가 증가하는 방향 (↓)
*/

struct dragon {
	int x;
	int y;
	int d;
	int g;
};

vector<vector<int>> map(101, vector<int>(101, 0)); // 100*100 맵
vector<dragon> dragonCurve;
int square = 0;
int n;
int x, y, d, g;

void countSquare() {
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (map[i][j] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j + 1] == 1) {
				square++;
			}
		}
	}
	return;
}

void drawDragon(int count) {
	
	if (count == n) {
		countSquare();
		return;
	}

	int gen = dragonCurve[count].g;

	vector<int> draw;

	int xx = dragonCurve[count].x;
	int yy = dragonCurve[count].y;

	draw.push_back(dragonCurve[count].d); // 최초 방향 push. 0세대의 경우를 말함

	map[yy][xx] = 1; // 최초 시작점을 1로 만듦
	
	for (int i = 0; i < gen; i++) {
		vector<int> temp;
		for (int j = draw.size()-1; j >= 0; j--) { // draw의 갯수만큼 역방향 반복
			if (draw[j] != 3) {
				temp.push_back(draw[j] + 1);
			}
			else {
				temp.push_back(0);
			}
		}
		
		for (int k = 0; k < temp.size(); k++) {
			draw.push_back(temp[k]);
		}
		
	}
	
	for (int i = 0; i < draw.size(); i++) {
		if (draw[i] == 0) {
			xx++;
			map[yy][xx] = 1;
		}
		else if (draw[i] == 1) {
			yy--;
			map[yy][xx] = 1;
		}
		else if (draw[i] == 2) {
			xx--;
			map[yy][xx] = 1;
		}
		else if (draw[i] == 3) {
			yy++;
			map[yy][xx] = 1;
		}
	}

	drawDragon(count + 1);
}



int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> x >> y >> d >> g;
		dragonCurve.push_back({ x, y, d, g });
	}

	drawDragon(0);

	cout << square;
	return 0;

}