문제 설명

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 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인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

문제 풀이

문제의 구현 자체는 별로 어렵지 않으나 규칙을 찾는 것이 어려워 시간을 많이 잡아먹은 문제였다. 세대를 거듭할수록 이전까지 그린 것을 회전시켜 끝점에 붙인다는 것이 잘 이해가 되지 않았는데, 처음에는 문제에서 요구한대로 이전까지 그린 것을 실제로 회전시켜볼까 했지만 연산을 어떻게 구현해야할지도 잘 모르겠고 너무 복잡해질 것 같아 포기했다.
두번째로 생각한 안은 규칙을 찾아 방향에 맞게 선을 하나하나 그리는 것이었는데 그 규칙을 찾을수가 없었다. 꽤 오랫동안 고민한 결과 이전의 것을 회전하여 끝점에 붙이면 우리는 지금까지 그린 것의 끝부분을 시계방향으로 회전시킨 것을 끝점에 붙이는 것부터 시작하여 시작 부분까지 뻗어나가게 된다. 즉 정리하자면 지금까지 그린 것의 회전방향을 끝에서부터 시작하여 처음까지 시계방향으로 90도 회전시킨 것을 하나씩 그려나가면 되는 것이다.
예를 들어 3 3 0 2 라는 입력이 주어졌다고 가정해보자.
우리는 3,3의 좌표에서 시작하여 방향이 0이므로 4,3에 점을 찍어 선을 긋게 될 것이다. 1세대 드래곤커브로 확장하자면 끝 점이 4,3이고 시계방향으로 회전시키므로 (계산의 편의를 위해 y축을 정방향으로 바꾼다고 가정하면) 다음 방향은 1이 될 것이다.
우리는 지금까지 0 1 의 방향으로 선을 그려왔다. 2세대로 확장하면 지금까지의 방향을 끝에서부터 시작하여 1을 회전시킨 2와 0을 회전시킨 1의 방향으로 선을 긋게 되고 총 0 1 2 1 의 방향으로 선을 긋게 된다. 만약 이것을 3세대로 확장시킨다고 가정하면 끝에서부터 2 3 2 1로 긋게 되어 총 0 1 2 1 2 3 2 1이 될 것이다.
이러한 규칙대로 드래곤 커브들을 확장시켜 그린 다음 각 좌표마다 정사각형의 개수를 세어 출력해주면 쉽게 정답을 도출해낼 수 있다. 자세한 코드는 다음과 같다.

코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};//각 방향에 따른 좌표이동

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int table[101][101]={0,};
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        int a,b,c,d; cin >> a >> b >> c >> d;
        vector<int> dir;
        table[a][b]=1;
        int xx=a+dx[c]; int yy=b+dy[c];
        table[xx][yy]=1; dir.push_back(c);//0세대는 먼저 그리고 시작
        for(int j=0; j<d; j++) {//세대에 맞게 확장
            int size=dir.size();
            for(int k=size-1; k>=0; k--) {//지금까지의 방향을 역순으로 순회
                int tmp=dir[k]+1;
                if(tmp>3) tmp=0;
                dir.push_back(tmp);
                xx=xx+dx[tmp]; yy=yy+dy[tmp];//끝점에서부터 확장
                table[xx][yy]=1;
            }
        }
    }
    int count=0;
    for(int i=0; i<100; i++) {
        for(int j=0; j<100; j++) {
            if(table[i][j]==1) {
                if(table[i+1][j] && table[i][j+1] && table[i+1][j+1]) count++;
            }
        }
    }//각 점에서부터 정사각형 개수 확인
    cout << count;
}