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

 

다신 보고 싶지 않지만 또 볼 것만 같은 문제..

 

해설을 찾아본 뒤에 풀어봤다.

 

이해가 어려우신 분들의 이해를 최대한 도와드리겠습니다.

 

이리저리 뒤집어서 생각하면 정말 어렵습니다.

일단 규칙을 하나로 정의합니다. 

 

 

➡️⬆️⬅️⬇️

이런 한 방향(시계 반대방향)으로 네모를 그린다고 생각해보세요.

그러면 오른쪽으로 시작하던 위로 시작하던 결국 똑같은 한 방향으로 그리게 되므로

이 방향 배열을 만들어 놓고, 인덱스를 어디서부터 시작할지로 결정하면 됩니다.

 

mx[4] = { 0, -1, 0, 1 };

my[4] = { 1, 0, -1, 0 };

 

mx[0], my[0] 부터 시작하면 오른쪽 방향부터 시작해서 네모를 그리게 되고

mx[1], my[1] 부터 시작하면 위쪽 방향부터 시작해서 네모를 그리게 됩니다. ( % 4 를 쓰면 되돌아 올 수 있겠죠? )

 

이 규칙을 정의했으니, 절반은 끝났습니다. 이제 어디서부터 시작하던 일정한 규칙을 정의할 수 있게 됩니다.

 

이제 드래곤 커브가 어떻게 정의되는지를, 한 방향의 시작을 기준으로만 정의해 주면

나머지 방향은 방금처럼 이미 규칙이 잘 정의되어 있으므로 해결이 됩니다.

 

예제에서처럼 동쪽에서부터 시작한다고 봤을떄

 

0세대 드래곤 커브 : 0

1세대 드래곤 커브 : 0 1

2세대 드래곤 커브 : 0 1 2 1

3세대 드래곤 커브 : 0 1 2 1 2 3 2 1

4세대 드래곤 커브 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

 

이런 규칙을 갖게 되는데

(각 숫자는 mx, my에 쓰이는 인덱스 입니다)

 

규칙은 이렇습니다.

 

2세대를 반으로 잘라 보겠습니다.

0 1 은 1세대 드래곤 커브의 값 그대로이고

2 1 은, 1세대 드래곤 커브의 0 1 의 순서를 뒤집어 1 0으로 만든 뒤 1씩 더한 값입니다.

 

즉, 이전 세대의 드래곤 커브의 값을 뒤쪽에서부터 돌면서 + 1 한 값을 새로 추가해주면 됩니다.

그리고 % 4를 통해 0 1 2 3 값 안쪽으로만 나오게 해주면 됩니다.

 

 

그리고

0세대 드래곤 커브는 값이 1개이고 (0)

1세대 드래곤 커브는 값이 2개이고 (0, 1)

2세대 드래곤 커브는 값이 4개이고 (0, 1, 2, 1)

 

이런식으로 2의 제곱수 만큼 증가하므로, 이를 계산해주면서 문제를 풀면 됩니다.

 

#include <iostream>
#include <cmath>
#include <vector>


using namespace std;

int N;
int t1, t2, t3, t4;

// 0 1 2 3 = 동 북 서 남
int mx[4] = {0, -1, 0, 1};
int my[4] = {1, 0, -1, 0};



bool map[101][101]; // 정사각형 체크용

vector<int> v;

int C;

// 10세대 까지 미리 만들어 놓기.
void dragon_curve() {
    
    // 예제에서 안내는 10세대 까지
    int G = 10;
    
    while(G--) {
        for(int i = v.size() - 1; i >= 0; i--)
            v.push_back((v[i] + 1) % 4);
    }
    
}

int main() {
    
    int x_, y_;
    
    cin >> N;
    
    v.push_back(0);
    
    dragon_curve();
    
    for(int i = 0; i < N; i++) {
        
        cin >> t1 >> t2 >> t3 >> t4;
        
        // 예제에서 x와 y가 반대이다.
        x_ = t2;
        y_ = t1;
        
        map[x_][y_] = true;
        
        for(int i = 0; i < pow(2, t4); i++) {
            
            x_ += mx[(v[i] + t3) % 4];
            y_ += my[(v[i] + t3) % 4];
            
            map[x_][y_] = true;
            
        }
        
    }
    
    
    for(int i = 0 ; i <= 100; i++) {
        for(int j = 0; j <= 100; j++) {
            if(map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1])
                C++;
        }
    }
    
    cout << C << "\n";
    
}