[BOJ 15685 // C++] 드래곤 커브

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15685번 문제인 드래곤 커브이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

이 문제를 풀기 위해서는 드래곤 커브가 길어지는 규칙을 효율적으로 나타낼 필요가 있다.

다음과 같은 관찰을 하자.

 

1) n세대 드래곤 커브를 구한 상태에서 n+1세대 드래곤커브의 점을 찾을 때, n+1세대의 각 변의 진행방향은 대응되는 n세대 드래곤커브의 변의 진행방향과 시계방향만큼 차이가 난다.

2) n세대 드래곤커브의 변의 개수를 l이라라 하면, n세대 드래곤 커브에서 n+1세대 드래곤 커브를 만들기 위해 이어붙이는 i번째 선분은 n세대 드래곤커브의 l-i번째 선분과 대응된다.

 

위의 관찰을 통해, 드래곤 커브가 길어질 때마다 스택에 이전 방향정보를 담아두고, 순서대로 꺼내 쓴다면 이 문제의 구현이 쉬워질 것이라는 것을 알 수 있다.

단, 스택에 있는 데이터를 꺼내서 쓰더라도 다음 세대의 드래곤커브를 만들 때 다시 사용해야하므로, 방향정보를 담아두는 스택은 따로 두고 다음 세대 드래곤 커브를 생성하기 시작할 때마다 그 스택을 복사해와서 사용해야 한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin;
using std::cout;

std::vector<int> stk;
std::vector<int> tempstk;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };

bool field[101][101];

void curve(int x, int y, int d, int g) { // 드래곤 커브가 지나는 좌표를 field에 기록한다
    stk.clear();
    tempstk.clear();
    stk.push_back(d - 1); // 첫 방향은 주어진 그대로 가기 위한 -1
    field[x][y] = true;
    while (g >= 0) {
        while (!stk.empty()) {
            int direction = stk.back() + 1;; stk.pop_back(); // 이전에 갔던 방향에서 회전
            if (direction > 3) direction -= 4;
            x += dx[direction];
            y += dy[direction];
            field[x][y] = true;
            tempstk.push_back(direction);
        }
        stk = tempstk;
        g--;
    }
}
int main()
{
    int N;
    cin >> N;
    for (int i = 0;i < N;i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        curve(x, y, d, g);
    }
    int ans = 0;
    for (int i = 0;i < 100;i++) { // field에 기록된 점에서 한변의 길이가 1인 정사각형을 탐색한다
        for (int j = 0;j < 100;j++) {
            if (field[i][j]) {
                if (field[i + 1][j] and field[i][j + 1] and field[i + 1][j + 1]) {
                    ans++;
                }
            }
        }
    }
    cout << ans;

    return 0;
}