백준 15685번: 드래곤 커브

문제

문제 바로가기> 백준 15685번: 드래곤 커브

풀이

vector에 방향을 저장해가며 90'을 회전시켜주는 방식으로 문제를 풀었다! vector에서 꺼낼 때는 다시 처음부터 이어 붙이는 것이므로 거꾸로 꺼내주어야 하는 것에 주의하자!

#include<iostream>
#include<vector>
#define MAX 101
using namespace std;

int N;
bool map[MAX][MAX];
int dy[] = { 0, -1, 0, 1 }; // 우 상 좌 하
int dx[] = { 1, 0, -1, 0 };

void solution(int x, int y, int d, int g) {

	vector<int> dir;

	// 시작점 
	map[y][x] = true;
	y += dy[d];
	x += dx[d];
	map[y][x] = true;
	dir.push_back(d);

	// g 세대 드래곤 커브 
	while (g--) {
		int curve_size = dir.size();
		for (int i = curve_size - 1; i >= 0; i--) { // 거꾸로 
			int nd = (dir[i] + 1) % 4;
			y += dy[nd];
			x += dx[nd];
			map[y][x] = true;
			dir.push_back(nd);
		}
	}
}

void output() {  // 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수
	int ans = 0;
	for (int i = 0; i < MAX - 1; i++) {
		for (int j = 0; j < MAX - 1; j++) {
			if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1]) ans++;
		}
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	while (N--) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		solution(x, y, d, g);
	}
	output();
}