[백준/BOJ]15685번 드래곤 커브

처음에 문제를 보고 예제그림의 x축과 y축이 내생각과 반대로 그려져서 한참을 헤맸던 문제. 

어려워 보여서 겁을 먹었던 문제였는데 규칙을 찾고 나니 즐겁게 푼 문제였다.

 

 

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

15685번: 드래곤 커브

해결 방법을 찾다가 처음에는 지금까지 이동하면서 찍어논 점들을 저장하고 각 점들을 기준점에서 90도 돌리는 방법을 생각했는데 찍어온 점의 히스토리가 꽤나 영향을 미쳐서 점들을 기준을 하면 이동시킨후의 위치를 찾는게

쉽지가 않았다. 따라서 상대적인 이동에 집중해서 이동한 점들을 기록하는게 아니라 이동한 방향을 기록해서 

끝 점에서  지금까지 이동한 방향을 역추적하여 90도 돌린 방향으로 이동하는 방법으로 풀었다.

 

내가 찾은 규칙은 

 

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

여기서 각 방향의 반대방향으로 뒤집은 뒤에 시계방향으로 90도 회전한 방향이 나아가야할 방향이었다. 

 

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

이 규칙을 찾았을 때 얼마나 기쁘던지 ㅎㅎ

 

 

 

 

 

<코드>

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
using namespace std;
int X[4] = { 1,0,-1,0 };
int Y[4] = { 0,-1,0,1 };

bool adj[105][105] = { false };

void move(int x, int y, int d, int g) {
	vector<int>dir;
	int sx = x, sy = y;
	adj[sx][sy] = true;
	int ge = 0;
	int pred;
	while (ge <= g) {
		if (ge == 0) {
		//	if (sx + X[d] >= 0 && sx + X[d] <= 100 && sy + Y[d] >= 0 && sy + Y[d] <= 100) {
				dir.push_back(d);
				pred = d;
				sx += X[d];
				sy += Y[d];
				adj[sx][sy] = true;
			//}
		//	else break;
		}
		else {
			int n = dir.size() - 1;
			for (int i = n; i >= 0; i--) {
				int ndir = (dir[i] + 5) % 4;
				dir.push_back(ndir);
				sx += X[ndir];
				sy += Y[ndir];
				adj[sx][sy] = true;
			}
		}
		ge++;
	}
	
}
int num(void) {
	int re = 0;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (adj[i][j] && adj[i][j + 1] && adj[i + 1][j] && adj[i + 1][j + 1])re++;
		}
	}
	return re;
}

int main(void) {
	int N;
	scanf("%d",&N);

	for (int i = 0; i < N; i++) {
		int x, y, d, g;
		scanf("%d %d %d %d", &x, &y, &d, &g);
		move(x, y, d, g);
	}
	printf("%d\n", num());
	return 0;
}