백준 15685번: 드래곤 커브

문제링크 :https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

 

 문제설명 

 

1. 첫째 줄에 드래곤 커브의 개수 N이 주어지고,  둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다.

2. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다.

  (x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다.)

3. 첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

 

 알고리즘 

 

1. 처음 주는 방향이 0이라고 한다면 그다음세대는 0 1 이고 그다음 세대는 0 1 2 1이다.

 

0세대 0

1세대 0 1

2세대 0 1 2 1

3세대 0 1 2 1 2 3 2 1

4세대 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

 

위 규칙을 이용하여 드래곤 커브를 그리고 정사가각형의 네 꼭짓점이 모두 드래곤 커브인 것을 찾아내면 된다.

 

 코드 

 

#include<iostream>
#include<vector>
using namespace std;
 
int map[101][101];
vector<int> v;
 
 
void func(int y, int x, int d, int g) {
    map[y][x] = 1;
 
    //0세대
    v.push_back(d);
 
    //배열 만들기
    for (int i = 0; i < g; i++) {
        int Size = v.size();
        vector<int> ex;
 
        for (int j = Size - 1; j >= 0; j--) {
 
            if (v[j] + 1 > 3) ex.push_back(0);
            else
                ex.push_back(v[j] + 1);
        }
 
        for (int j = 0; j < Size; j++) {
            v.push_back(ex[j]);
        }
 
    }
    int Size = v.size();
    int yy = y, xx = x;
 
    //드래곤 커브 그리기
    for (int i = 0; i < Size; i++) {
        if (v[i] == 0) {
            xx++;
        }
        else if (v[i] == 1) {
            yy--;
 
        }
        else if (v[i] == 2) {
            xx--;
        }
 
        else if (v[i] == 3) {
            yy++;
        }
        map[yy][xx] = 1;
    }
 
 
    for (int i = 0; i < Size; i++)v.pop_back();
}
 
//사각형 확인 함수
int square() {
    int result = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1])result++;
        }
    }
    return result;
}
 
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y, d, g;
 
        cin >> x >> y >> d >> g;
        func(y, x, d, g);
 
    }
 
 
    cout << square();
}