[C++] 백준/Gold/15685. 드래곤 커브

드래곤 커브 (백준 15685번)

문제 요약
격자 위에 여러 드래곤 커브를 그린 뒤, 정사각형 네 꼭짓점이 모두 드래곤 커브에 포함되는 개수를 구하는 문제이다.

1. 문제 분석

• 드래곤 커브 정의
  • 세대 $g=0$인 드래곤 커브는 시작점 $(x,y)$에서 방향 $d$로 한 칸 이동한 두 점을 잇는 선분이다.
  • 세대가 한 번 증가할 때마다, 기존 커브의 “끝점”을 기준으로 90도 시계 회전시킨 복제 선분을 뒤에 이어 붙여 커브를 확장한다.
• 목표
  • 주어진 $n$개의 드래곤 커브를 모두 그린 뒤,
  • 격자 $(i,j),(i+1,j),(i,j+1),(i+1,j+1)$ 네 점이 모두 드래곤 커브 상에 표시된 칸(점)인 정사각형의 개수를 세어 출력.

2. 핵심 아이디어

1. 드래곤 커브 생성 (세대별)
   • 기본 세대$(g=0)$: 두 점 $(x,y)), ((x+\Delta_x,,y+\Delta_y)$을 찍고 시작.
   • 회전 함수:
     • 현재까지 찍은 점들의 리스트를, “끝점”을 중심으로 90° 시계 방향으로 회전시켜 새로운 점들을 구한다.
     • 회전 변환:
       $$\begin{pmatrix} x' \ y' \end{pmatrix}
       \begin{pmatrix} x_0 - (y - y_0) \ y_0 + (x - x_0) \end{pmatrix}$$
       여기서 $(x_0,y_0)$는 직전 세대의 끝점, $(x,y)$는 변환 전 점.
   • 매 세대마다, 회전된 점들을 뒤집어서(reverse) 기존 리스트 뒤에 이어 붙인다.
2. 격자 표시
   • $101\times101$ 크기 grid[y][x]에, 드래곤 커브가 지나간 모든 점을 true로 표시.
3. 정사각형 개수 세기
   • 모든 $(i,j)$에 대해
     $$\text{grid}[i][j]\ \wedge\ \text{grid}[i][j+1]\ \wedge\ \text{grid}[i+1][j]\ \wedge\ \text{grid}[i+1][j+1]$$
     가 모두 true인 경우를 카운트.

3. 코드 구조

// (1) 방향 오프셋: 0=→,1=↑,2=←,3=↓
int offset[4][2] = {{0,1},{-1,0},{0,-1},{1,0}};
vector<vector<bool>> grid(101, vector<bool>(101,false));

// (2) 한 세대에서 "회전"으로 확장할 점들을 계산
vector<pair<int,int>> Rotation(vector<pair<int,int>>& Curve) {
    auto [ox,oy] = Curve.back();  // 기준점(끝점)
    vector<pair<int,int>> newPts = Curve;
    for (auto& [x,y] : newPts) {
        int dx = x - ox, dy = y - oy;
        // 90° 시계 회전 변환
        x = ox - dy;
        y = oy + dx;
    }
    reverse(newPts.begin(), newPts.end());
    return newPts;
}

// (3) 하나의 커브를 g세대까지 그리는 함수
void MakeDragonCurve(int x, int y, int d, int g) {
    vector<pair<int,int>> curve;
    // 세대 0: 시작점과 한 칸 이동한 점
    curve.push_back({x,y});
    curve.push_back({x+offset[d][1], y+offset[d][0]});
    grid[y][x] = grid[y+offset[d][0]][x+offset[d][1]] = true;

    // 세대 반복
    while (g--) {
        auto nextPts = Rotation(curve);
        // 중복되는 첫 점을 제외하고 새 점들만 이어 붙임
        for (int i = 1; i < nextPts.size(); ++i) {
            auto [nx,ny] = nextPts[i];
            curve.push_back({nx,ny});
            grid[ny][nx] = true;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    while (n--) {
        int x,y,d,g; 
        cin >> x >> y >> d >> g;
        MakeDragonCurve(x,y,d,g);
    }

    // (4) 정사각형 개수 세기
    int answer = 0;
    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 100; ++j) {
            if (grid[i][j] && grid[i][j+1]
             && grid[i+1][j] && grid[i+1][j+1]) {
                ++answer;
            }
        }
    }
    cout << answer;
}