[BOJ] 15685. 드래곤 커브

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

다들 쉽다고 하는 문제인데 나는 개인적으로 쉽지는 않았다. 실제로 규칙만 금방 알아내면 어렵지는 않다.

하지만 나는 일단 x좌표가 열이고 y좌표가 행이라 처음에 너무 헷갈렸었다....

일반적인 수학에서는 원래 그렇긴하지만 코딩할 때는 보통 r,c이면 r이 행이니까...ㅠ

그리고 처음에 규칙을 좌표에서 찾느라 헤매기도 했다...

 

 

이 문제는 세대별로 방향에 규칙이 있다.

문제의 예시를 봐보자.

0세대 드래곤 커브의 방향이 0이었다면, 1세대에 새로 생기는 방향은 1이다.

그리고 다음 2세대에 새로 생기는 방향은 순서대로 2, 1 이다.

그리고 다시 3세대에는 2, 3, 2, 1 방향이 새로 생긴다.

 

정리해서 보면 다음과 같다.

0세대 : 0

1세대 : 0 1

2세대 : 0 1 2 1

3세대 : 0 1 2 1 2 3 2 1 

 

 

3세대로 예를 들어보면 다음과 같이 방향이 1씩 증가했음을 알 수 있다.

화살표가 이어진 점은 화살표의 출발점이 이전 세대의 원래 점이고

화살표가 가르키는 점이 90도 회전해서 새로 생기는 점이다.

즉, 이전에 있었던 점의 방향으로부터 1이 더해졌음을 알 수 있다.

 

1세대와 2세대도 다시 보면 같은 규칙을 가지고 있는 것을 알 수 있다.

위의 규칙을 이용해서 방향 index를 문제에서 주어진 대로 dx와 dy배열에 잘 저장해서 구현해주면 된다.

 

 

드래곤 커브를 구했으면 이제 각 칸의 정사각형의 네 꼭짓점이 드래곤 커브에 포함되는지를 구해줘야한다.

드래곤 커브끼리 겹치는 부분이 있을 수도 있으므로 드래곤 커브를 먼저 모두 구한 뒤에 나중에 한번에 계산해준다.

 

(0,0)부터 시작하여 시작점으로부터 오른쪽, 아래, 오른쪽아래가 드래곤 커브에 포함되어 있는지 검사해주면 된다.

맨 마지막행이나 열에서 범위를 넘어가지 않도록 99번째 행과 99번째 열까지만 검사를 진행한다.

 

 

#include <iostream>
#include <vector>
using namespace std;
 
bool check[101][101];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
int x, y, d, g;
vector<int> dir;
 
 
int calc() {
    int cnt = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            //네 꼭짓점을 검사
            if (!check[i][j]) continue;
            if (!check[i + 1][j]) continue;
            if (!check[i][j + 1]) continue;
            if (!check[i + 1][j + 1]) continue;
 
            //모두 포함되어 있다면 cnt 증가
            cnt++;
        }
    }
 
    return cnt;
}
 
 
 
void solve() {
    //0세대 처리
    check[y][x] = true;
    x += dx[d];
    y += dy[d];
    check[y][x] = true;
    dir.push_back(d);
 
 
    int dsize;
    //구해줄 세대 수만큼 진행
    for (int i = 0; i < g; i++) {
        dsize = dir.size();
 
        //회전하여서 이번 세대에서 새로 생길 방향들을 추가해준다.
        for (int j = dsize - 1; j >= 0; j--) {
            dir.push_back((dir[j] + 1) % 4);
        }
 
        dsize = dir.size();
        //새로 생긴 방향들에 대해서만 이동을 진행
        for (int j = (dsize / 2); j < dsize; j++) {
            x += dx[dir[j]];
            y += dy[dir[j]];
            check[y][x] = true;
        }
    }
 
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    while (n-- > 0) {
        cin >> x >> y >> d >> g;
        
        //새로운 드래곤 커브를 구해 줄 것이므로 방향을 저장해 놓을 벡터를 비워준다. 
        dir.clear();
        solve();
    }
 
 
    //드래곤 커브를 모두 구하고 한 번에 계산해준다
    cout << calc() << '\n';
 
    return 0;
}