백준 15685 - 드래곤 커브(C++)

문제 링크입니다. https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

삼성 SW 역량테스트 문제입니다.

문제 조건

출력 예시

문제를 풀기 위해서는 2가지를 알아야합니다.

1. 드래곤 커브 구현하기

2. 정사각형 갯수 세기

 

먼저 드래곤 커브를 구현 하겠습니다.

위의 그림을 통해 설명하겠습니다.

1세대에서 2세대로 넘어갈 경우, 1세대의 움직임에서 반시계 방향으로 90도 움직인 방향으로 먼저 움직인 뒤, 1세대의 방향으로 움직입니다.

2세대에서 3세대로 넘어갈 경우, 2세대의 움직임에서 2번, 1번 순으로 반시계 방향으로 90도 움직인 방향으로 먼저 움직인 뒤,  2세대 방향으로 움직입니다.

이런 방식으로 움직입니다

그렇다면 0세대에서 1세대로 넘어갈 때는 어떻게 되는지 확인해보겠습니다.

오른쪽으로 움직이는게 반시계 방향으로 90도 움직인 방향으로만 움직이는 것을 볼 수 있습니다.

 

지금까지의 결론을 내보자면

1. 0세대에서 1세대로 갈 경우에는 이동횟수가 변하지 않는다.

2. 1세대부터 다음세대로 넘어갈때, 반시계 방향으로 움직인 뒤, 이전 세대 방향으로 움직인다.

 

드래곤 커브를 움직일 때마다 이전 세대의 이동 방향을 사용한다는 것을 알 수 있습니다.

따라서 vector를 이용해서 계속 이동 방향을 저장해주는 것이 중요합니다.

 

해당 과정을 N번의 드래곤 커브 세대와 같아질 때까지 반복해주면 됩니다.

(drangon_curve 함수 참고해주세요)

 

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

이제 정사각형 갯수를 세는 방법을 확인하겠습니다.

 

정사각형 특징은 (X , Y)가 1일때 (X + 1 , Y) , (X  , Y + 1) , (X + 1 , Y + 1) 이렇게 4개 좌표값이 모두 1이여야 합니다.

MAP의 범위가 0 ~ 100까지이니, 0 ~ 99까지 2중 for문을 통해 정사각형을 확인해주면 됩니다.

(count_square 함수를 참고해주세요)

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

// d가 0일 경우 오른쪽 / 1일 경우 -> 위쪽 / 2일 경우 -> 왼쪽 / 3일 경우 -> 아래쪽

int N;
typedef struct info {
	int x;
	int y;
	int d;
	int g;
}info;
int map[101][101];
vector<info> curve;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };

void dragon_curve(int num, int gen, int x, int y, vector<int> dir) {
	if (gen == 0) {
		x = x + dx[dir[0]];
		y = y + dy[dir[0]];
		map[x][y] = 1;
	}
	else {
		for (int i = 0; i < dir.size(); i++) {
			x = x + dx[dir[i]];
			y = y + dy[dir[i]];
			map[x][y] = 1;
		}
	}
	if (gen == curve[num].g) return;
	if (gen == 0) {
		dir[0]++;
		if (dir[0] == 4) dir[0] = 0;
	}
	else {
		int k = dir.size();
		vector<int> new_dir;
		for (int i = k - 1; i >= 0; i--) {
			int xx = dir[i] + 1;
			if (xx == 4) xx = 0;
			new_dir.push_back(xx);
		}
		for (int i = 0; i < k; i++) {
			new_dir.push_back(dir[i]);
		}
		dir.clear();
		dir = new_dir;
	}
	dragon_curve(num, gen + 1, x, y, dir);
}

int count_square() {
	int square = 0;
	for (int i = 0; i <= 99; i++) {
		for (int j = 0; j <= 99; j++) {
			if (map[i][j] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j + 1] == 1) {
				square++;
			}
		}
	}
	return square;
}

void solve() {
	for (int i = 0; i < curve.size(); i++) {
		map[curve[i].y][curve[i].x] = 1;
		vector<int> dir;
		dir.push_back(curve[i].d);
		dragon_curve(i, 0, curve[i].y, curve[i].x, dir);
	}
	int ans = count_square();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		curve.push_back({ x,y,d,g });
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!