문제

문제 링크

해설

(개인적으로는 Chapter 5 구현 문제들 중 가장 어려웠습니다. 이번 문제 덕분에 기하문제는 어렵게 생각하지 말고 규칙성 파악 후 단순 구현하면 되는 것이란 걸 배웠습니다.)

• 문제의 표현 중 '드래곤 커브를 끝점을 기준으로 시계 방향으로 90도 회전시킨 다음 끝점에 붙인 것이다' 라는 표현 때문에 함정에 빠지기 쉬운 문제였습니다.
• 일단, 좌표를 신경쓰지 말고, <예제 입력 1>을 대략 4세대까지 구해봅시다.
  
• 규칙성이 대략적으로 보입니다. (이전 세대의 방향을 뒤집은 것 + 1) % 4 한 것을 앞쪽 절반, 이전 세대 그대로를 뒤쪽 절반에 붙이면 다음 세대의 방향을 구할 수 있습니다.
• 프로그램이 시작될 때, 미리 4방향에 대해 0~10세대에 대한 방향 정보를 구해놓은 뒤, 주어지는 드래곤 커브 입력에 대해 격자판에 체크표시 한 뒤 드래곤 커브로 둘러싸인 사각형 개수를 체크하면 됩니다.
  • 이때 (y, x), (y, x + 1), (y + 1, x), (y + 1, x + 1) 네 모서리가 모두 체크 된 곳이 있을 때 사각형이라고 판단하면 됩니다.
  • 유효한 격자의 좌표가 100x100까지 이므로, 최대 102x102 짜리 배열을 만들어놓으면 OutOfBounds 오류를 예방할 수 있습니다.
• 어려운 기하 문제는 코딩테스트 수준에서는 나올 가능성이 거의 없다고 합니다. 위 문제처럼, 규칙성을 판단한 뒤 구현하는 것 만으로도 어렵기 때문입니다.

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 102;
constexpr int DIRECTION[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

int N, answer;
vector<int> dragon[4][11];
vector<vector<bool>> arr(MAX, vector<bool>(MAX));

void initialization() {
    for (int dir = 0; dir < 4; ++dir) {
        dragon[dir][0].push_back(dir);            // 0세대
        dragon[dir][1].push_back((dir + 1) % 4);  // 1세대
        for (int gen = 2; gen <= 10; ++gen) {     // 2~10세대
            int n = dragon[dir][gen - 1].size();
            for (int i = n - 1; i >= 0; --i)    // 현재 세대 앞 절반은 이전 세대 역순 + 시계방향 90도 회전
                dragon[dir][gen].push_back((dragon[dir][gen - 1][i] + 1) % 4);
            for (int i = 0; i < n; ++i)         // 현제 세대 뒷 절반은 이전 세대 그대로
                dragon[dir][gen].push_back(dragon[dir][gen - 1][i]);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> N;
    initialization();
    for (int i = 0; i < N; ++i) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        
        arr[y][x] = true;
        for (int gen = 0; gen <= g; ++gen) {
            for (const int& dir : dragon[d][gen]) {
                y += DIRECTION[dir][0];
                x += DIRECTION[dir][1];
                arr[y][x] = true;
            }
        }
    }
    for (int y = 0; y < MAX; ++y)
        for (int x = 0; x < MAX; ++x)
            if (arr[y][x] && arr[y + 1][x] && arr[y][x + 1] && arr[y + 1][x + 1]) answer++;

    cout << answer;
}

소스코드 링크

결과