문제 설계 단계
드래곤 커브 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);
}