백준 15685 - 드래곤 커브

문제링크

• 백준 15685

문제설명

• 0세대 드래곤 커브는 길이가 1인 선분이고, 방향성을 가진다.
  • 0: x좌표가 증가하는 방향
  • 1: y좌표가 감소하는 방향
  • 2: x좌표가 감소하는 방향
  • 3: y좌표가 증가하는 방향
• 1세대 드래곤 커브는 0세대 드래곤 커브의 모양에서 끝점을 잡고 시계방향으로 90도 회전시킨 후 끝점에 붙인다.
• 2세대 드래곤 커브는 1세대 드래곤 커브의 모양에서 끝점을 잡고 시계방향으로 90도 회전시킨 후 끝점에 붙인다.
• …
• 10세대 드래곤 커브까지 존재한다.
• 1x1 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력하라.

입력

• 드래곤 커브 개수 N이 주어진다.
• N개의 줄에 걸쳐 드래곤 커브 시작점(x,y), 시작 방향(d), 세대(g)가 주어진다.

문제접근

• 규칙성을 찾는 것이 중요하다.
  • 드래곤 커브가 어떤 방식으로 그려지는지 선분을 긋는 방향을 중심으로 규칙을 찾았으나, 규칙이 항상 성립할 수 있는 이유를 확신하지 못하여 문제를 푸는데 시간이 오래 걸렸다.
• 규칙성을 쉽게 떠올리지 못했던 이유는 세대를 거듭할수록 점의 개수가 많아지고, 회전하는 모양도 복잡했기 때문이다.
• 끝점을 포함하는 선분은 4가지의 방향성을 가지고 있고, 끝점을 잡고 돌려서, 끝점에 붙인다는 것을 통해 문제를 단순하게 생각하면, 그 어떤 드래곤 커브 모양이든 끝점을 포함한 마지막 선분은 회전 후 부착 시 4가지 방향 중 하나로 결정된다.
• 이 원리를 모든 선분에 대해서 적용하여 방향을 결정짓고, startX, startY 로부터 최종 드래곤 커브 모양까지 경로를 기억하면 된다.

구현(All Pass)

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// dir 0, 1, 2, 3 => x++, y--, x--, y++
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int map[102][102] = { 0, };

void SetDragonCurve(int startX, int startY, int d, int g) {
	vector<int> direction;
	stack<int> s;
	direction.push_back(d);

	for (int gen = 1; gen <= g; gen++) {
		for (auto ele : direction)
			s.push(ele);
		int dir;
		
		while (!s.empty()) {
			dir = s.top();
			dir = (dir + 1) % 4;
			direction.push_back(dir);
			s.pop();
		}
	}

	map[startX][startY] = 1;
	int curX = startX, curY = startY;
	for (int i = 0; i < direction.size(); i++) {
		curX = curX + dx[direction[i]]; // i번째 좌표에서 i+1번째 좌표로 만들기
		curY = curY + dy[direction[i]];
		// cout << "[" << curX << ", " << curY << "]" << endl;
		map[curX][curY] = 1;
	}

}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int N, x, y, d, g;
	cin >> N;

	for (int line = 0; line < N; line++) {
		cin >> x >> y >> d >> g;
		SetDragonCurve(x, y, d, g);
	}

	int ans = 0;
	for (int r = 0; r <= 100; r++) {
		for (int c = 0; c <= 100; c++) {
			if (map[r][c] && map[r][c + 1] && map[r + 1][c] && map[r + 1][c + 1])
				ans++;
		}
	}
	cout << ans << endl;

	return 0;
}