BOJ 15685 · 드래곤 커브

알고리즘 분류 : 시뮬레이션  

문제에 주어진 조건 그대로 드래곤 커브를 만들어서 사각형의 개수를 세는 문제다. 드래곤 커브를 만드는 규칙을 파악해야 한다.

• 드래곤 커브는 최대 10세대까지 있으며, 일정한 규칙에 따라 만들어진다.
• 1. N세대 드래곤 커브를 만든다고 가정하자.
• 2. N-1세대 드래곤 커브를 우선 복사하고, 이것을 시계 방향으로 90도 회전시킨다.
• 3. 회전 시킨 드래곤 커브를 N-1세대 드래곤 커브의 마지막에 이어 붙인다.
• 위 1~3 과정을 10세대까지 반복하면 된다.

• 쉽게 구현하기 위해서, 드래곤 커브를 좌표 대신 방향을 사용한다.
• 방향은 0(→) 1(↑) 2(←) 3(↓) 이다.
• 첫 출발 방향을 0으로 둔다.
• 이전 세대의 마지막 방향에서 출발 방향까지 거꾸로 탐색하면서, 각 방향에 1을 더하고 이어 붙인다. (%4 연산 필요)
• 위 방법으로 드래곤 커브를 미리 10세대까지 만들어둔다.
• 이후에 입력받은 방향과 드래곤 세대만큼 좌표에 체크해둔다.
• 마지막으로, 사각형 좌표 (X,Y) (X+1,Y) (X,Y+1) (X+1,Y+1)를 체크해서 모두 존재하면, 정답을 1 카운트한다.
• (0, 0)부터 (100,100)까지 모두 확인한 후, 정답 개수를 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <vector>
using namespace std;

int n, x, y, d, g, ans;
vector<int> v;
bool a[101][101];
const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

// Make all dragon curve (~10th generation)
void dragon() {
    v.push_back(0);
    for (int i=1; i<=10; i++) {
        int k = 1<<(i-1);
        for (int j=0; j<k; j++) {
            v.push_back((v[k-j-1]+1)%4);
        }
    }
}

// Draw dragon curves by input.
void solve() {
    a[x][y] = true;
    for (int i=0; i<(1<<g); i++) {
        x += dx[(v[i]+d)%4], y += dy[(v[i]+d)%4];
        a[x][y] = true;
    }
}

// Count squares.
void count() {
    for (int i=0; i<100; i++) {
        for (int j=0; j<100; j++) {
            if (a[i][j] && a[i+1][j] && a[i][j+1] && a[i+1][j+1]) ans++;
        }
    }
}

int main() {
    dragon();
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d %d %d %d", &x, &y, &d, &g);
        solve();
    }
    count();
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

v, ans = [0], 0
a = [[0]*101 for _ in range(101)]
dx, dy = (1, 0, -1, 0), (0, -1, 0, 1)

for i in range(1, 11):
    k = 1<<(i-1)
    for j in range(k):
        v.append((v[k-j-1]+1)%4)

for _ in range(int(input())):
    x, y, d, g = map(int, input().split())
    a[x][y] = 1
    for i in range(1<<g):
        x, y = x+dx[(v[i]+d)%4], y+dy[(v[i]+d)%4]
        a[x][y] = 1

for i in range(100):
    for j in range(100):
        if a[i][j] and a[i+1][j] and a[i][j+1] and a[i+1][j+1]:
            ans += 1
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 15685