boj_15685_드래곤커브

pdot715·2018년 10월 24일
0

문제 설계 단계

드래곤 커브 3가지 속성
- 시작점
- 시작방향
- 세대

y좌표 x좌표
(1, 3) (1, 4), (2, 3), (2, 4)
(2, 2) (2, 3), (3, 2), (3, 3)


좌표가 0부터니까
(y, x) (y, x + 1), (y + 1, x), (y + 1, x + 1)이 모두 true이면
사각형이 생성된 것임.
이걸 0, 0에서부터 돌려주면 판정 가능함.

0세대의 드래곤커브의 경우
시작점(y, x)를 True로 바꿔주고
방향이 0이면 x++ (y, x + 1) (0)
방향이 1이면 y-- (y - 1, x) (1)
방향이 2이면 x-- (y, x - 1) (2)
방향이 3이면 y++ (y + 1, x) (3)


2세대의 드래곤 커브인 경우
1세대의 방향(0->1)
추가되는 방향 방향(2->1) 순서로 추가

90도 회전하면 0, 1이었던게

3세대의 드래곤커브인경우
방향이 0이면 2세대 드래곤커브가 방향이(0->1->2->1) 이면
추가되는 방향은(2->3->2->1)
역순으로 생각하면

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

즉 드래곤 커브가 주어지면...
지금까지 주어졌던 방향 정보 push할 벡터
큐에 모두 push하고
그 다음 단계는 pop하면서 + 1 방향 하면서 벡터에는 푸쉬
이 역할을 하는 함수를 만들면...

bool MAP[100 + 1][100 + 1];



방향이 0이면 (0, 1, 2, 1) -> 2 / 4번째가 같음(1/3번째는 반대)
방향이 1이면 (1, 0, 0, 3) -> 2 / 3번째가 같음( 1/3번째는 반대)
방향이 2면 (2, 1, 1, 0) -> 2 / 3번째가 같음(1/4번째는 반대)
방향이 3이면 (3, 0, 1, 0) -> 2 / 4번째가 같음(1/3번째는 반대)

1세대의 드래곤커브인 경우
방향이 0이면 맨처음 시작점 기준으로 (y-1, x+1)
방향이 1이면 맨처음 시작점 기준으로 (y-1, x+1)
방향이 2이면 맨처음 시작점 기준으로 (y-1, x-1)
방향이 3이면 맨처음 시작점 기준으로 (y+1, x+1)

2세대의 드래곤커브인 경우
방향이 0이면 맨처음 시작점 기준으로(y - 1, x) (y-2, x)

3세대의 드래곤커브인 경우
방향이 0이면 맨처음 시작점 기준으로 (y-1, x - 1) / (y-2, x -1) / (y -1, x - 2) / (y -2 , x - 2)

4세대의 드래곤커브인경우...

삽질 포인트

  • 드래곤커브의 변화 단계를 예제보다 좀 더 해봐야했음... 변화 규칙은 다음세대에서는 역순으로 반시계방향으로 90도 증가하는 것이었음.
  • 이전 세대의 길이만큼 계속 다음 세대에 적용해야하기때문에 v2.clear()는 필요없었음

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool MAP[100 + 1][100 + 1];

struct DC {
	int y;
	int x;
	int d;
	int g;
};

int N;

DC dc[20 + 1];



/*

방향정보 저장
방향정보 바탕으로 이동
다음 방향정보 저장 (반시계방향으로 90도를 역순으로 저장)

0
0->1
01->21로 이동

이동할때 벡터로 저장
vector<int> v1
vector<int> v2

v1.push_back()
v1.pop()
하고 뒤에서부터 v >= 0까지 하면 될듯?


*/

void curve(int y, int x, int s_arrow, int sede) {

	MAP[y][x] = true;
	vector<int> v1; // 방향정보 저장 1번 (지금 방향 정보)
	vector<int> v2; // 방향정보 저장 2번 (다음 방향 정보)
	v1.push_back(s_arrow);


	int cnt = 0;
	while (cnt <= sede) {
	//	printf("세대 : %d\n", cnt);
		for (int i = 0; i < v1.size(); i++) {
			if (v1[i] == 0) {
				x++;
				MAP[y][x] = true;
			}
			else if (v1[i] == 1) {
				y--;
				MAP[y][x] = true;
			}
			else if (v1[i] == 2) {
				x--;
				MAP[y][x] = true;
			}
			else if (v1[i] == 3) {
				y++;
				MAP[y][x] = true;
			}
			v2.push_back(v1[i] < 3 ? v1[i] + 1 : 0);
		}

		v1.clear();
		for (int i = v2.size() - 1; i >= 0; i--) {
		//	printf("%d ", v2[i]);
			v1.push_back(v2[i]);
		}
//		printf("\n");
		// v2.clear();

		cnt++;


	}




}




int result = 0;

int check() {
	int tmp_result = 0;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (MAP[i][j] && MAP[i][j + 1] && MAP[i + 1][j] && MAP[i + 1][j + 1]) {
				tmp_result++;
			}
		}
	}

	return tmp_result;
}


int main() {


	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d %d", &dc[i].x, &dc[i].y, &dc[i].d, &dc[i].g);
	}
	
	for (int i = 0; i < N; i++) {
		curve(dc[i].y, dc[i].x, dc[i].d, dc[i].g);
	}

	result = check();

//	for (int i = 0; i < 10; i++) {
//		for (int j = 0; j < 10; j++) {
	//		printf("%d ", MAP[i][j]);
//		}
	//	printf("\n");
//	}
	
	printf("%d", result);



}
profile
개발자지망

0개의 댓글