[BOJ] 15685 : 드래곤 커브

문제 링크

15685번: 드래곤 커브 (acmicpc.net)

15685번: 드래곤 커브

단순한 구현 문제.

 

풀이

한 점에서 시작된 커브를 한 세대마다 시계방향으로 90도 회전하여 이어붙인 모양을 드래곤 커브라고 한다.

나는 한 세대 한 세대 지날때마다 커브를 그리는 게아니라 g번째 세대까지 그렸을 때 커브의 방향을 벡터에 저장해두고 한번에 그리는 방식으로 진행했다.

처음에 커브를 직접 그려보면서 규칙을 파악했다.

시계방향으로 90도 회전한 후 커브의 진행방향은 어떻게 바뀌는지 살펴보면

1. x좌표가 증가하는 방향 (→) 은 회전 후 y좌표가 감소하는 방향 (↑) 으로 바뀐다.

2. y좌표가 감소하는 방향 (↑) 은 회전 후 x좌표가 감소하는 방향 (←) 으로 바뀐다.

3. x좌표가 감소하는 방향 (←) 은 회전 후 y좌표가 증가하는 방향 (↓) 으로 바뀐다.

4. y좌표가 증가하는 방향 (↓) 은 회전 후 x좌표가 증가하는 방향 (→) 으로 바뀐다.

이 규칙을 이용해서 g세대 드래곤 커브를 이루는 진행방향을 순서대로 벡터에 저장했다.

단, 기존의 저장된 방향을 회전 후에 이어붙이는 것처럼 구현하려면 기존의 벡터에서 뒤에서 부터 값을 꺼내 회전한 후벡터에 추가해주어야 한다.

예를 들어 예시에 나온 3세대 드래곤 커브는

(0,0)에서 시작해서

→ ,↑, ← ,↑, ← ,↓, ← ,↑ 순서대로 진행하면 3세대 드래곤 커브를 그릴 수 있다.

이 방향을 벡터에 저장한 후 한 번에 그려주었다. 벡터에 저장된 방향 순서대로 이동하면서 드래곤 커브에 포함되는 좌표는 visited배열에 true로 표시했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100 + 5;
bool Map[MAX_N][MAX_N];
int N;
 
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
 
void dragon_curve(int x, int y, int d, int g);
bool is_ans(int x, int y) {
    if (Map[x][y] && Map[x + 1][y] && Map[x][y + 1] && Map[x + 1][y + 1])
        return true;
    return false;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        dragon_curve(x, y, d, g);
    }
    int ans = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (is_ans(i, j))
                ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}
int change_direction(int d) {
    if (d == 0) return 1;
    else if (d == 1) return 2;
    else if (d == 2) return 3;
    else if (d == 3) return 0;
}
void dragon_curve(int x, int y, int d, int g) {
    vector<int> direction;
    direction.push_back(d);
    for (int i = 1; i <= g; i++) { //generation
        for (int j = direction.size() - 1; j >= 0; j--) {
            direction.push_back(change_direction(direction[j]));
        }
    }
    Map[x][y] = true;
    for (int i = 0; i < direction.size(); i++) {
        x += dx[direction[i]];
        y += dy[direction[i]];
        Map[x][y] = true;
    }
}

그리고 만약 한 변의 길이가 1인 정사각형 네 꼭지점이 모두 true로 표시되어있으면 그 정사각형은 드래곤 커브에 포함된 것으로 인지했다.