백준 15685 드래곤 커브 [Simulation]

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

15685번: 드래곤 커브

문제 풀이

간단하게 정리해보면,

1. 입력을 받는다.

2. 입력받은 (x, y, d, g)에 맞는 드래곤 커브를 만든다.

3. 모든 드래곤 커브를 만든 후, 답을 구한다.

 

1번은 쉽고, 2번이랑 3번은 고민을 해봐야 합니다.

입력을 받은 (x, y, d, g)를 어떻게 하면 드래곤 커브를 그릴 수 있을까?를 고민해보면 다음과 같습니다.

만약에 g가 0으로 들어오면 한 번만 드래곤 커브를 그리면 되고,

만약에 g가 1로 들어오면 0세대, 1세대 이렇게 2번의 드래곤 커브를 그리면 됩니다.

즉, g는 해당 드래곤 커브의 반복 횟수를 의미하고

 

중요한 것은 d(시작 방향)입니다.

예를 들어 (0,0,0,2)가 들어왔다고 하면 (문제의 설명 예시에 있어요!)

(0, 0)에서 시작 방향이 0인 (1, 0)을 그리게 됩니다. 이것이 바로 0세대입니다.

 

(0, 0) - (1, 0)  => 0세대

 

이때 기억해야 할 것은 끝점인 (1, 0)과 방향(0)

--------------------------------------------------------------------------------------------------------------------

1세대부터는 반복해서 다음과 같이 작업합니다.

 

0세대에서 사용했던 방향을 얻어와서 + 1을 해줍니다. 그것이 바로 다음 세대의 시작 방향이 됩니다.

 

기존에 저장한 끝점인 (1, 0)에서 방향(1)을 계산해주면 (1, -1)이 됩니다.

          (1, -1)

            |        => 1세대

(0, 0) - (1, 0)

 

이때 기억해야 할 것은 끝점인 (1, -1), 방향(1, 0)

--------------------------------------------------------------------------------------------------------------------

마찬가지로 세대를 반복해줍니다.

기존에 저장한 끝점인 (1, -1)에서 방향 (2)을 계산해주면 (0, -1)이 됩니다.

또, 아직 방향이 남아있으므로 끝점인(0, -1)에서 방향 (1)을 계산해주면 (0, -2)이 됩니다.

 

(0, -2)

   |

(0, -1) - (1, -1)

            |        => 2세대

(0, 0) - (1, 0)

--------------------------------------------------------------------------------------------------------------------

설명이 조금 어렵게 했는데 정리하면

한 세대를 끝내면 끝점과 방향을 저장해두었다가,

다음 세대가 올 때 끝점에다가 방향을 +1을 해주고 계산을 해줍니다.

0세대 = 끝점(1, 0) 방향 (0) -> 다음 세대를 계산할 때는 끝점 + 방향(0 + 1)

1세대 = 끝점(1,-1) 방향 (1, 0) -> 다음 세대를 계산할 때는 끝점 + 방향 (1 + 0, 0 + 1)

2세대 = 끝점(0,-2) 방향 (1, 2, 1, 0) -> 다음 세대를 계산할 때는 끝점 + 방향 (1 + 1, 2 + 1, 1 + 1, 0 + 1)

... N세대

 

 

정답을 구하는 방법은 0<=X, Y<=100 이므로

한 좌표를 X1, Y1이라고 하면

(X1, Y1)     (X1, Y1+1)

(X1+1, Y1) (X1+1,Y1+1) 이 모두 true라면 그때 count를 1증가하는 방식으로 해주면 됩니다.

소스 코드

#include <iostream>
#include <vector>
using namespace std;

int N;
bool a[101][101];

int dy[] = { 0,-1,0,1 };
int dx[] = { 1,0,-1,0 };

int calculateDirection(int d)
{
	if (d + 1 <= 3) return d + 1;
	else return 0;
}

void dragonCurve(int x, int y, int d, int g)
{
	a[y][x] = true;
	vector<int> now_direction, next_direction, temp;
	// 0세대를 먼저 계산해준다.
	int now_x = x + dx[d];
	int now_y = y + dy[d];
	now_direction.push_back(d);
	a[now_y][now_x] = true;

	// 1세대 ~ g세대까지 계산
	for (int i = 1; i <= g; i++)
	{
		next_direction.clear(); temp.clear();
		for (int j = 0; j < now_direction.size(); j++)
		{
			// 기존 세대에 사용했던 방향을 가져와서 +1을 해줍니다.
			d = now_direction[j];
			if (d + 1 >= 4) d = 0;
			else d = d + 1;

			// 다음 그릴 커브의 좌표를 구하고
			int next_x = now_x + dx[d];
			int next_y = now_y + dy[d];
			// 경계 체크
			if (next_x >= 0 && next_y >= 0 && next_x <= 100 && next_y <= 100)
			{
				now_x = next_x;
				now_y = next_y;
				a[now_y][now_x] = true;
				next_direction.push_back(d);
			}
		}
		// 1. 다음 세대의 방향을 역순으로 temp에 넣어주고,
		// 2. 그 temp에 기존의 세대에 사용했던 방향을 순서대로 넣어줍니다.
		// 3. 그리고 현재 방향을 temp로 해주면 됩니다.
		for (int j = next_direction.size() - 1; j >= 0; j--) temp.push_back(next_direction[j]);
		temp.insert(temp.end(), now_direction.begin(), now_direction.end());
		now_direction = temp;
	}
}

int countDragonCurve()
{
	/*
	x1 x2
	x3 x4
	*/
	int cnt = 0;
	for (int i = 0; i <= 100; i++)
	{
		for (int j = 0; j <= 100; j++)
		{
			pair<int, int> x1 = { i,j };
			pair<int, int> x2 = { i, j + 1 };
			pair<int, int> x3 = { i + 1, j };
			pair<int, int> x4 = { i + 1,j + 1 };
			if (x2.first < 0 || x2.second < 0 || x2.first > 100 || x2.second > 100) continue;
			if (x3.first < 0 || x3.second < 0 || x3.first > 100 || x3.second > 100) continue;
			if (x4.first < 0 || x4.second < 0 || x4.first > 100 || x4.second > 100) continue;
			if (a[x1.first][x1.second] && a[x2.first][x2.second] && a[x3.first][x3.second] && a[x4.first][x4.second]) cnt++;
		}
	}
	return cnt;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		dragonCurve(x, y, d, g);
	}

	int ans = countDragonCurve();
	cout << ans;
	return 0;
}