[백준] 15685번 드래곤 커브 (C++, 삼성 기출)

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

간단한 구현 문제이다.
방향을 기준으로 저장해 풀었다.

그림을 자세히 보면 규칙이 있다.
세대가 지날수록 그 전 세대에 그려진 것의 역순으로 90도 회전(방향 + 1) 을 해주면 된다.
예를 들어, 2세대에서 0 1 2 1 로 진행한다.
그 다음 세대인 3세대에선 0 1 2 1 의 역순으로 1 2 1 0 이 뒤에 붙게 되는데, 이 값의 1을 더한 값 (90도 회전)을 붙여주면 된다.

코드는 아래와 같다.

if (depth != 0) {
		for (int i = v.size() - 1; i >= 0; i--) {
			q.push((v[i] + 4 + 1) % 4);
		}
	}

이후에, 큐에 저장한 값을 pop하면서 이동 후 map에 표시해준다.
현재 정보는 다음 세대에서 사용해야하므로 vector에 담아서 다음세대에 전달한다.

코드는 아래와 같다.

int nx = x; int ny = y;
	while (!q.empty()) {
		// 큐에 있는 값으로 이동을 해주면서 map에 표시
		// 다음 세대에 현재까지의 정보가 필요하므로 
		// vector에 담아 다음 세대에 전달
		int direction = q.front();
		v.push_back(direction);
		q.pop();
		nx += dir[direction][0];
		ny += dir[direction][1];
		map[ny][nx] = 1;
	}

전체 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
int dir[4][2] = { {1,0}, {0,-1}, {-1,0}, {0,1} };
int map[101][101];
int answer = 0;

// 정사각형이 있는지 확인
void get_square() {
	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)
				answer++;
		}
	}
}

void dragon_curv(int x, int y, int d, int g, int depth,  vector<int>& v) {
	// 처음 정한 세대까지 그렸을 때 종료
	if (g + 1 == depth) {
		return;
	}
	// 새로운 커브를 큐에 역순으로 저장
	// 방향은 90도 회전한 값으로 +1해줌
	queue<int> q;
	if (depth != 0) {
		for (int i = v.size() - 1; i >= 0; i--) {
			q.push((v[i] + 4 + 1) % 4);
		}
	}
	// 처음에는 그냥 방향값을 넣어준다.
	else q.push(d);

	int nx = x; int ny = y;
	while (!q.empty()) {
		// 큐에 있는 값으로 이동을 해주면서 map에 표시
		// 다음 세대에 현재까지의 정보가 필요하므로 
		// vector에 담아 다음 세대에 전달
		int direction = q.front();
		v.push_back(direction);
		q.pop();
		nx += dir[direction][0];
		ny += dir[direction][1];
		map[ny][nx] = 1;
	}
	dragon_curv(nx, ny, d, g, depth + 1, v);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y, d, g;
		vector<int> v;
		cin >> x >> y >> d >> g;
		map[y][x] = 1;
		dragon_curv(x, y, d, g, 0, v);
	}

	get_square();
	cout << answer;
}