백준 15685번 드래곤 커브

 

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

처음 문제를 이해할 때 드래곤 커브가 다음 세대로 가는 경우 끝 점을 기준으로 시계 방향으로 90도 회전시킨다는 말을 반대로 이해해가지고 헷갈렸다. 끝 점을 시계 바늘의 중심 축이라 생각하고 그 축을 기준으로 드래곤 커브를 시계방향으로 90도 회전시키면 된다는 뜻으로 받아들이니 이해하기 쉬웠다.

 

문제는 다음과 같은 규칙이 있다.

- g세대에서 드래곤 커브의 길이는 2^(g)이다.

- 드래곤 커브는 현재까지 이동했던 방향을 기준으로 다음 세대가 어디에 그려질지 결정된다.

예를 들어 0세대에서 시작방향이 1이고 3세대까지 간다고 가정하면 아래와 같은 규칙을 찾을 수 있다.

 

0세대 : 0

1세대 : 0 (1)

2세대 : 0 1 (2 1)

3세대 : 0 1 2 1 (2 3 2 1)

 

괄호친 부분은 이전 세대에서 이동했던 방향을 기준으로 정해진 다음 세대로 가는 방향을 의미한다.

다시 말해, 1세대까지 완료된 드래곤 커브는 0, 1이라는 방향을 거쳐서 만들어졌다면 그 다음 2세대 드래곤 커브는 1세대 방향 수열 값에 1씩 더한 뒤 역으로 이동하면 된다. 여기서 방향은 최대 4가지이므로 4를 넘어가면 나머지 연산으로 방향 3의 다음 방향은 0이다.

 

 

접근 순서는 다음과 같다.

1. g세대까지 가기 위한 이동방향 수열을 계산한다. (수열의 길이는 2^g가 된다.)

 

2. 방향 수열을 따라 map에 드래곤 커브를 그린다.

(중간중간 이동할 때마다 그리는 것보다 방향 수열을 완벽히 구한 다음에 한 번에 그리는게 편하다.)

 

3. 드래곤 커브의 수 n만큼 위 과정을 반복한다.

 

 

방향 수열을 구하기 위해 2중 for문과 vector, stack을 사용하였다.

아래는 특정 드래곤커브가 g세대 까지 어느 방향으로 이동하는지에 대한 방향 수열을 구하는 과정이다.

 

시작 방향 d가 입력으로 주어지므로 vector v에 저장한다.

그 뒤 v의 크기만큼 for문을 반복하여 다음 이동방향(temp)을 stack s에 저장한다.

그 뒤 s에 들어있던 값을 v에 push_back하여 순서대로 방향 수열을 저장한다.

	v.push_back(d);

	for (int j = 0; j < g; j++) {

		int vec_size = v.size();

		for (int k = 0; k < vec_size; k++) {
			temp = (v[k] + 1) % 4;
			s.push(temp);
		}

		for (int k2 = 0; k2 < vec_size; k2++) {
			v.push_back(s.top());
			s.pop();
		}

	}

 

 

 

g세대까지의 방향 수열이 정해지면 map에 드래곤 커브를 그려준 뒤에 다음 드래곤 커브를 위해 v와 s를 비워준다.

map의 크기는 100x100 격자이지만 입력으로 들어오는 x, y는 2차원 배열의 좌표가 아닌 2차원 평면의 좌표 값이기 때문에 격자를 벗어나는지 판단하는 조건에서 ny<100이 아니라 ny<=100이 되어야 한다.

// 정해진 경로에 따라 map에 드래곤 커브 그리기
		for (int i = 0; i < v.size(); i++) {
			dir = v[i];

			ny = ny + dy[dir];
			nx = nx + dx[dir];
			
			if (ny >= 0 && ny <= 100 && nx >= 0 && nx <= 100) {
				map[ny][nx] = 1;
			}

		}

		

		// 벡터랑 스택 비우기
		while (!v.empty()) v.pop_back();
		while (!s.empty()) s.pop();

 

 

 

 

 

 

 

전체코드

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int n, x, y, d, g;
int map[101][101];
int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };
int temp;
int res = 0;
stack<int> s;
vector<int> v;

int main() {
	
	ios::sync_with_stdio(false);

	cin >> n;

	
	while (n--) {
		cin >> x >> y >> d >> g;
		
		map[y][x] = 1;
		

		//세대가 끝날때까지 움직이는 모든 경로 구하기
		v.push_back(d);

		for (int j = 0; j < g; j++) {

			int vec_size = v.size();

			for (int k = 0; k < vec_size; k++) {
				temp = (v[k] + 1) % 4;
				s.push(temp);
			}

			for (int k2 = 0; k2 < vec_size; k2++) {
				v.push_back(s.top());
				s.pop();
			}

		}
					
		
		int dir;
		int ny = y;
		int nx = x;
			

		// 정해진 경로에 따라 map에 드래곤 커브 그리기
		for (int i = 0; i < v.size(); i++) {
			dir = v[i];

			ny = ny + dy[dir];
			nx = nx + dx[dir];
			
			if (ny >= 0 && ny <= 100 && nx >= 0 && nx <= 100) {
				map[ny][nx] = 1;
			}

		}

		

		// 벡터랑 스택 비우기
		while (!v.empty()) v.pop_back();
		while (!s.empty()) s.pop();

		
	}



	// 정답 계산하기
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (map[i][j]==1 && map[i][j+1]==1 && map[i+1][j]==1 && map[i+1][j+1]==1) {
				res++;
			}
		}
	}

	cout << res;

	return 0;
}