<Baekjoon> #15685 구현_드래곤 커브 c++

#15685 드래곤 커브
참고

💬IDEA

• 문제에서 주어진 대로 각 세대마다 방향 표시를 나타내보면

0: x좌표가 증가하는 방향 (→)
1: y좌표가 감소하는 방향 (↑)
2: x좌표가 감소하는 방향 (←)
3: y좌표가 증가하는 방향 (↓)

0세대: 0
1세대: 01
2세대: 0121
3세대: 01212321 
......

과 같이 나타낼 수 있다.
규칙을 찾아보자면 n세대는 n-1세대 + n-1세대 길이만큼의 무언가 이다
여기서 n-1세대 길이만큼의 무언가는 잘 보면 규칙을 찾을 수 있다.
n-1세대를 거꾸 나타낸 것에서 각 자리에 +1 이다. 정확히 말하면 (+1)%4이다

위에서 2세대는 0121이다. 그렇다면 3세대는 0121 + 2세대를 거꾸로 한 것 (+1%)4
즉 0121을 거꾸로한 1210에 각 자리수에 1을 더해주고 4를 나눠준 값을 0121뒤에 쓴다. 따라서 0121 2321이 된다

👩‍💻1. make Curve

• 먼저 dir_info에는 각 세대마다 방향에 관한 정보를 포함한다.
• makeCurve()함수 에서는 현재 dir_info에 저장되어 있는 세대의 다음 세대를 만들어 준다. 즉, dir_info에 2세대 방향 정보 {0121}가 들어있다면 {2321}을 추가로 덧붙여 {01212321}을 만들어주는 함수다

void makeCurve() {
	int s = dir_info.size();
	for (int i = s - 1; i >= 0; i--) {
		int nd = (dir_info[i] + 1) % 4;
		y = y + dy[nd];
		x = x + dx[nd];

		map[y][x] = 1;

		dir_info.push_back(nd);
	}
}

• 드래곤 커브의 끝점마다 1로 표시해주어 드래곤 커브가 지나간 자리라는 것을 표시해준다

• makeCurve()를 호출할 때는 먼저
  ⓐ입력받은 (y,x)좌표에 점을 찍어주고 map[y][x]=1,
  ⓑ(y,x)에서 입력받은 방향 d로 한 칸 이동한 좌표를 다시 (y,x)로 만들어주고
  ⓒ해당 지점에 map[y][x]=1를 해준다.
  ⓓ이렇게 처음 입력받은 y,x,d 좌표에 의해 0세대가 만들어진다.
  ⓔ그 후 g에 따라 g만큼 반복해서 makeCurve()함수를 호출한다.

	for (int i = 0; i < N; i++) {
		cin >> x >> y >> d >> g;
		dir_info.clear();

		map[y][x] = 1; //ⓐ
		y = y + dy[d]; //ⓑ
		x = x + dx[d]; //ⓑ
		map[y][x] = 1; //ⓒ
		dir_info.push_back(d); //ⓓ

		for (int j = 0; j < g; j++) //ⓔ
			makeCurve();
	}

👩‍💻2. count()

• 네 꼭지점이 모두 드래곤 커브에 일부인 것의 개수를 출력해야 하므로 사각형 모양으로 인접한 네 지점이 모두 map상에서 1 인 것을 찾는다

void count() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (map[i][j] == 1 && map[i + 1][j] == 1 &&
				map[i][j + 1] == 1 && map[i + 1][j + 1] == 1) cnt++;
		}
	}
}

전체코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 101;
int dy[] = { 0,-1,0,1 };
int dx[] = { 1,0,-1,0 };
vector<int> dir_info;
int map[MAX][MAX];
int N, x, y, d, g;
int cnt;

void count() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (map[i][j] == 1 && map[i + 1][j] == 1 &&
				map[i][j + 1] == 1 && map[i + 1][j + 1] == 1) cnt++;
		}
	}
}

void makeCurve() {
	int s = dir_info.size();
	for (int i = s - 1; i >= 0; i--) {
		int nd = (dir_info[i] + 1) % 4;
		y = y + dy[nd];
		x = x + dx[nd];
		
		map[y][x] = 1;

		dir_info.push_back(nd);
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y >> d >> g;
		dir_info.clear();

		map[y][x] = 1;
		y = y + dy[d];
		x = x + dx[d];
		map[y][x] = 1;
		dir_info.push_back(d);

		for (int j = 0; j < g; j++)
			makeCurve();
	}
	count();
}

int main() {
	solution();
	cout << cnt << endl;
	return 0;
}