[백준]드래곤커브

시뮬레이션 문제이고 크게 생각할 부분은 2가지였다.

1.길을 어떻게 붙일것인가? (회전을 어떤 방식으로 시킬것인가)

2.정사각형의 개수를 어떻게 셀것인가?

길을 붙이는 것에 대해서는 첫째로 끝점을 기준으로 90도 시계방향으로 회전한 점을 구해야 겠다고 생각했고,

회전행렬을 곱해 점을 알아내려고 시도했었다. 하지만 이 방법은 계속 기준점을 갱신해주어야 해서 까다롭다고

생각했다. (이방식으로도 할수는 있을거 같다.)

다음으로는, 길을 붙이는것에 대해서 그냥 한칸한칸 전진하다고 생각하고 화살표를 그려보니 일정한 규칙이 있었다.

그동안 간 경로의 방향들에 대해서 최신의 경로들부터 쭈루룩 시계방향으로 돌려서 가주면 된다는 것이었다.

정사각형의 개수를 세주는 것에서는 네 점이 모두 1이어야 정사각형이 존재하므로 한 기준점에서 나머지 3점을 

검사해서 모두 1일때만 카운트를 해주었다.

 

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

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

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

 

 

#include <iostream>
#include<vector>
using namespace std;
 
int N;
int dx[] = {1,0,-1,0}, dy[] = { 0,-1,0,1 };
int map[101][101];
vector<int> path;
 
int Change(int d) { return (d + 1) % 4; }
 
void solve(int x, int y, int d, int g) {
    map[y][x] = 1; //출발
    x = x + dx[d], y = y + dy[d];
    map[y][x] = 1; //처음꺼는 이동
    path.push_back(d);
 
    for (int m = 0; m < g; m++) {
        //세대 수 만큼 반복
        for (int s = path.size() - 1; s >= 0; s--) {
            int nd = Change(path[s]); //시계방향으로 회전
            path.push_back(nd);
            x = x + dx[nd], y = y + dy[nd];
            map[y][x] = 1; //이동
        }
    }
    path.clear();
}
 
int COUNT() {
    int answer = 0;
    for (int i = 0; i < 101; i++) for (int j = 0; j < 101; j++) if (map[i][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j] == 1 && map[i + 1][j + 1] == 1) answer++;
    return answer;
}
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y, d, g;
        scanf_s("%d%d%d%d", &x, &y, &d, &g);
        solve(x,y,d,g);
    }
    cout << COUNT() << endl;
    return 0;
}