[백준] 15685번 드래곤 커브

15685번 드래곤 커브

---

1. 이해하기

• 드래곤 커브의 다음 세대가 변하는 규칙을 찾아야 한다.
  • 
  • 규칙을 보면 가장 최근에 추가된 방향부터 차례대로 90도 반시계 방향 회전해서 다음 세대에 추가하는 것을 볼 수 있다.
• 규칙대로 드래곤 커브를 표시해주고 표시된 것 중 사각형의 갯수를 찾아서 출력해 주면 된다.
• 시뮬레이션 문제.

---

2. 구현하기

• 드래곤 커브의 다음 세대를 구해 반환해준다.

  vector<int> get_next_cur(vector<int> cur) {
      vector<int> ret = cur;
      int size = cur.size();
      for(int i = 0; i < size; i++) {
          int dir = cur.back(); cur.pop_back();
          dir = (dir+1)%4;
          ret.push_back(dir);
      }
      return ret;
  }

• 드래곤 커브의 방향을 구한 것을 바탕으로 배열에 표시해준다.

  void solve(vector<int> cur, int x, int y) {
      int size = cur.size();
      map[x][y] = true;
      for(int i = 0; i < size; i++) {
          int dir = cur[i];
          x+=dx[dir]; y+=dy[dir];
          map[x][y] = true;
      }
  }

• 배열에서 사각형의 갯수를 반환해준다.

  bool is_square(int x, int y) {
      return map[x][y] and map[x][y+1] and map[x+1][y] and map[x+1][y+1];
  }
  
  int get_square_cnt() {
      int ret = 0;
      for(int i = 0; i < 100; i++) {
          for(int j = 0; j < 100; j++) {
              if(is_square(i,j)) ret++;
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <vector>
using namespace std;
bool map[101][101];
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

vector<int> get_next_cur(vector<int> cur) {
    vector<int> ret = cur;
    int size = cur.size();
    for(int i = 0; i < size; i++) {
        int dir = cur.back(); cur.pop_back();
        dir = (dir+1)%4;
        ret.push_back(dir);
    }
    return ret;
}

bool is_square(int x, int y) {
    return map[x][y] and map[x][y+1] and map[x+1][y] and map[x+1][y+1];
}

int get_square_cnt() {
    int ret = 0;
    for(int i = 0; i < 100; i++) {
        for(int j = 0; j < 100; j++) {
            if(is_square(i,j)) ret++;
        }
    }
    return ret;
}

void solve(vector<int> cur, int x, int y) {
    int size = cur.size();
    map[x][y] = true;
    for(int i = 0; i < size; i++) {
        int dir = cur[i];
        x+=dx[dir]; y+=dy[dir];
        map[x][y] = true;
    }
}

int main() {
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) {
        int y,x,d,g;
        cin >> y >> x >> d >> g;
        vector<int> cur;
        cur.push_back(d);
        for(int i = 1; i <= g; i++) {
            cur = get_next_cur(cur);
        }
        solve(cur,x,y);
    }
    cout << get_square_cnt() << '\n';
    return 0;
}