[BOJ][C++] 15685 드래곤커브

문제

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

15685번: 드래곤 커브

풀이

- 커브 그리기

 1. 0단계를 먼저 그려줍니다. 저는 dx, dy 배열을 주고 dir에 따라서 다음 좌표를 그려줬어요. map을 bool로 두고 그렸습니다.

 2. 입력받은 depth를 종료조건으로, dfs로 단계마다 커브를 그렸습니다.  90도 회전하는 nxtx, nxty 배열을 만들어주고 회전을 시켰어요. 이때, 끝점을 계속 기억해주고 업데이트를 해줘야합니다. 좌표값을 저장하고있는 끝점에서 거슬러 올라가면서 i좌표와 i-1좌표의 차이를 파악한 뒤, 기억해놓은 끝점에 회전값(nxtx, nxty을 적용한 값)을 적용시켜야해요. 

 3. 사각형모양으로 모두 true일 경우 answer++를 해줍니다.

코드

#include <iostream>
#include <vector>
using namespace std;
bool map[101][101];
int note[21][4];
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
int nxtx[] = { 1,0,-1,0 };
int nxty[] = { 0,-1,0,1 };
int answer = 0;
void dfs(int cnt, vector<pair<int, int>> v, int depth) {
	if (cnt == depth) {
		return;
	}
	int vsize = v.size();
	int x = v[vsize - 1].first;
	int y = v[vsize - 1].second;
	for (int i = vsize - 1; i > 0; i--) {
		int vx = v[i - 1].first - v[i].first;
		int vy = v[i - 1].second - v[i].second;
		int nx, ny;
		if (vx == 1 && vy == 0) {
			nx = x + nxtx[1];
			ny = y + nxty[1];
		}
		else if (vx == 0 && vy == -1) {
			nx = x + nxtx[2];
			ny = y + nxty[2];
		}
		else if (vx == -1 && vy == 0) {
			nx = x + nxtx[3];
			ny = y + nxty[3];
		}
		else {
			nx = x + nxtx[0];
			ny = y + nxty[0];
		}
		map[nx][ny] = true;
		v.push_back(make_pair(nx, ny));
		x = nx;
		y = ny;
	}
	dfs(cnt + 1, v, depth);
}
int main() {
	//입력
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> note[i][0] >> note[i][1] >> note[i][2] >> note[i][3];
	}
	//커브 그리기
	for (int i = 0; i < n; i++) {
		//0세대
		int y = note[i][0]; int x = note[i][1];
		int dir = note[i][2]; int depth = note[i][3];
		map[x][y] = true;
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		map[nx][ny] = true;

		vector<pair<int, int>> v;
		v.push_back(make_pair(x, y)); v.push_back(make_pair(nx, ny));
		//다음 세대
		dfs(0, v, depth);
		/*for (int p = 0; p < 12; p++) {
			for (int q = 0; q < 12; q++) {
				cout << map[p][q] << ' ';
			}
			cout << endl;
		}
		cout << "-------------------" << endl;*/
	}

	//정사각형 갯수 구하기
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			//cout << map[i][j] << ' ';
			if (map[i][j] == true &&
				map[i + 1][j] == true &&
				map[i][j + 1] == true &&
				map[i + 1][j + 1] == true) {
				answer++;
			}
		}
		//cout << endl;
	}

	cout << answer;