백준 15685 C++

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

 

첫 인상이 굉장히 무서운 문제다.

드래곤 커브가 무엇인지도 잘 모르겠고 설명도 이상한데 생긴건 또 무섭다.

 

그래도 시도하면 할 만한 문제다.

일단 드래곤 커브가 격자 밖으로 나가지 않아서 귀찮은 문제가 1개 줄었다.

 

그리고 다음 문제가 결국 '드래곤 커브를 어떻게 그릴 것인가'이다.

종이에 그리다보면 나올 것이라고 생각되는데 말로 설명하기가 참 어렵다.

 

이전까지 있었던 방향을 저장하고 역순으로 조회하며 (dir+1) % 4하면 된다.

아 물론 dir+1은 dy, dx를 어떻게 했느냐에 따라 다르지만 아래 코드는 그렇게 된다.

한번 예제 1번만이라도 코드를 따라가보면 무슨 규칙인지 감이 올 것이다.

 

#include <bits/stdc++.h>

using namespace std;

int dc, result = 0;
int sx, sy, sd, g;
int points[105][105];
vector<int> pastDir;
int dy[] = { 0, -1, 0 ,1 };
int dx[] = { 1, 0, -1, 0 };

void Dragon(int x, int y, int dir, int g)
{
	//최초 상태 -> g=0일 때 point찍음.
	points[y][x] = 1;
	int ny = y + dy[dir];
	int nx = x + dx[dir];
	points[ny][nx] = 1;
	pastDir.push_back(dir);

	while (g) {
		g--;
		for (int i = pastDir.size() - 1; i >= 0; i--){		//뒤에서부터 불러온다.
			dir = (pastDir[i] + 1) % 4;
			ny = ny + dy[dir];
			nx = nx + dx[dir];
			points[ny][nx] = 1;
			pastDir.push_back(dir);
		}
	}
}

void FindSquere()
{
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (points[i][j] && points[i + 1][j] && points[i][j + 1] && points[i + 1][j + 1]) {
				result++;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> dc;
	for (int i = 0; i < dc; i++) {
		pastDir.clear();
		cin >> sx >> sy >> sd >> g;
		Dragon(sx, sy, sd, g);
	}

	FindSquere();

	cout << result;
}