15685번 드래곤 커브

처음 시도한 방법은 90회전의 중심이 되는 점을 잡고, 일일이 이동하려고 했다. 아래는 미완성 코드..

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <stack>
#include <tuple>
#include <deque>
using namespace std;

int map[101][101];
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };
void f() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cout << map[j][i] << " ";
		}
		cout << '\n';
	}
	cout << '\n';
}
int main() {
	freopen("in1.txt", "rt", stdin);
	int t;
	cin >> t;
	while (t--) {
		deque<pair<int, int> > S1;
		deque<pair<int, int> > S2;
		int x, y, d, g;
		cin >> y >> x >> d >> g;
		S1.push_back(make_pair(x, y));
		S1.push_back(make_pair(x + dx[d], y + dy[d]));
		map[x][y] = 1;
		map[x + dx[d]][y + dy[d]] = 1;
		S2 = S1;
		while (g > 0) {
			//f();
			int tmp1, tmp2;
			bool ok = false;
			bool ok2 = true;
			int x2, y2;
			S1 = S2;
			int L = S2.size();
			for (int i = 0; i < L; i++) {
				cout << S2.front().first << "," << S2.front().second << '\n';
				S2.push_back(S2.front());
				S2.pop_front();
			}
			tie(x, y) = S1.back(); 
			cout << '\n' << x << " , " << y << '\n';
			cout << '\n';
			S1.pop_back();
			while (!S1.empty()) {
				tie(x2, y2) = S1.front();
				S1.pop_front();
				x2 = x2 - x;
				y2 = y2 - y;
				int temp = x2;
				x2 = y2;
				y2 = temp * (-1);
				x2 = x2 + x;
				y2 = y2 + y;
				if (x2 > 100 || x2 < 0 || y2 > 100 || y2 < 0) {
					ok = true;
					while (!S1.empty()) S1.pop_front();
					break;
				}
				S2.push_back(make_pair(x2, y2));
			}
			if (ok) break; //break일수도
			//Q에 넣고 map에 적용하기 전, 범위를 벗어나는지 계속 체크
			//벗어나면 걍 끝
			//S1.push_front(make_pair(tmp1, tmp2));
			S1 = S2;
			while (!S1.empty()) {
				tie(x, y) = S1.front();
				map[x][y] = 1;
				S1.pop_front();
			}
			g--;
		}
		
	}
	int ans = 0;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (map[i][j] == 0) continue;
			if (map[i + 1][j] == 0) continue;
			if (map[i][j + 1] == 0) continue;
			if (map[i + 1][j + 1] == 0) continue;
			ans++;
		}
	}
	cout << ans << '\n';
	f();
	return 0;
}

하지만, 규칙성을 찾아내고 좌표나 도움이 되는 값을 계속 들고 있는 것이 무척 도움이 되고, 편리하다.
ex)
방향 좌표를 v벡터에 계속 저장한다.
0세대 : 0
1세대 : 0 1
2세대 : 0 1 2 1
3세대 : 0 1 2 1 2 3 2 1
이렇게 K세대를 저장할때, K-1세대의 끝에서부터 (v[i]+1)%4 값이 저장된다. 이를 이용하여 방향을 넣고, x,y값을 계속해서 들고있으면 쉽게 커브를 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
int dx[] = { 0,-1,0,1 };
int dy[] = { 1,0,-1,0 };
vector<int> v;
int x, y, d, g;
int map[101][101];
void go() {
	map[x][y] = 1;
	x = x + dx[d];
	y = y + dy[d];
	map[x][y] = 1;
	v.push_back(d);
	for (int k = 0; k < g; k++) {
		int L = v.size();
		for (int i = L - 1; i >= 0; i--) {
			int nd = (v[i] + 1) % 4;
			x = x + dx[nd];
			y = y + dy[nd];
			map[x][y] = 1;
			v.push_back(nd);
		}
	}
}
int main() {
	//freopen("in1.txt", "rt", stdin);
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> y >> x >> d >> g;
		v.clear();
		go();
	}
	int ans = 0;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (map[i][j] == 0) continue;
			if (map[i + 1][j] == 0) continue;
			if (map[i][j + 1] == 0) continue;
			if (map[i + 1][j + 1] == 0) continue;
			ans++;
		}
	}
	cout << ans << '\n';
	return 0;
}