[백준] 15685번 드래곤 커브

15685번: 드래곤 커브

문제에 나와 있는 예제인

(0, 0)에서 시작하는 0방향 0세대 드래곤 커브가 3세대까지 그려지는 과정은

 

<0세대>

끝점(1, 0)을 향해 0방향(오른쪽)을 가리키는 모양이다.

다음 세대를 위해 시작점을 가리키는 방향으로 뒤집어주면

2방향(왼쪽)을 가리키는 모양이 된다.

 

0세대 끝점 : (1, 0)

방향 : 2←

 

<1세대>

0세대의 끝점(1, 0)을 기준(고정)으로 시계 방향으로 90도 회전한 모양이다.

1세대의 끝점은 (1, -1)이 되고

다음 세대를 위해 시작점을 가리키는 방향으로 뒤집어주면

3방향(아래쪽)을 가리키는 모양이 추가된다.

 

1세대 끝점 : (1, -1)

방향(끝점부터) : 3↓ 2←

 

<2세대>

1세대의 끝점(1, -1)을 기준(고정)으로 시계 방향으로 90도 회전한 모양이다.

2세대의 끝점은 (0, -2)가 되고

다음 세대를 위해 시작점을 가리키는 방향으로 뒤집어주면

3방향(아래쪽), 0방향(오른쪽)을 가리키는 모양이 추가된다.

 

2세대 끝점 : (0, -2)

방향(끝점부터) : 3↓ 0→ 3↓ 2←

 

<3세대>

2세대의 끝점(0, -2)를 기준(고정)으로 시계 방향으로 90도 회전한 모양이다.

3세대의 끝점은 (-2, -2)가 되고

다음 세대를 위해 시작점을 가리키는 방향으로 뒤집어주면

3방향(아래쪽), 0방향(오른쪽), 1방향(위쪽), 0방향(오른쪽)을 가리키는 모양이 추가된다.

 

3세대 끝점 : (-2, -2)

방향(끝점부터) : 3↓ 0→ 1↑ 0→ 3↓ 0→ 3↓ 2←

 

이렇게 이전 세대의 방향들을 90도 회전 후 반대로 뒤집어준 방향들과

이전 세대의 방향들을 합친게

다음 세대의 방향들이라는 방식을 이용하여 구현하면 된다.

 

이때 방향들을 모두 한 번에 처리하는 게 아니라

맨 앞에 있는 방향부터 90도 회전시킨 후 가리키는 정점을 현재 끝점으로 갱신하고

그 방향을 반대로 뒤집어준 뒤 다음 세대에 추가하는 과정이 반복된다는 점에서

스택을 이용하면 쉽게 구현할 수 있다.

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int N, x, y, d, g, X, Y, cnt;
int arr[101][101], dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, -1, 0, 1 }, d_reverse[4] = { 2, 3, 0, 1 }, d_rot[4] = { 3, 0, 1, 2 };
int main() {
	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> x >> y >> d >> g;
		arr[x][y] = 1; //시작점 표시
		x += dx[d], y += dy[d]; //시작점에서 d방향
		arr[x][y] = 1; //끝점 표시
		stack <int> tmp;
		vector <int> v;
		v.push_back(d_reverse[d]), tmp.push(d_reverse[d]); //끝점->시작점 인 형태로 방향을 저장
		for (int i = 1; i <= g; i++) {
			while (!tmp.empty()) {
				x+= dx[d_rot[tmp.top()]], y+= dy[d_rot[tmp.top()]]; //끝점 갱신
				arr[x][y] = 1;
				v.push_back(d_reverse[d_rot[tmp.top()]]);
				tmp.pop();
			}
			for (int j = 0; j < v.size(); j++) tmp.push(v[j]);
		}
	}
	for (int i = 0; i < 100; i++) { //정사각형 개수 찾기
		for (int j = 0; j < 100; j++) {
			if (arr[i][j] == 1 && arr[i + 1][j] == 1 && arr[i][j + 1] == 1 && arr[i + 1][j + 1] == 1) cnt++;
		}
	}
	cout << cnt;
	return 0;
}