15685번 드래곤 커브

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

첫번째 생각.

첫번째 예제 1을 보자.

4 2 1 3 을 예로 들어 생각해보자. 4,2에 위 방향이고 총 3단계 커브를 거친다.

이떄, 4,2를 기준점으로 잡고 위 방향으로 먼저 0단계를 거친다. 그럼 (4,2)와 (4,1)이 존재하는데 이것을  기준점 (4,2)를 기준으로 90도 회전 시킨다. 그다음에 끝점을 맞춰 줘야 하는데, 서로간의 끝점(4,1)과 (5,2)의 차이인 (1,1)을 빼줌으로써 맞출 수 있지 않을까?

딱봐도 너무 복잡하다. 좀 더 간단한 방법을 생각해야 한다.

다른 생각.

방향을 기준으로 어떤 규칙이 있지 않을까?

예를 들어 4 2 1 3 에서 처음 0단계에서 위

1단계에서 위 왼쪽

2단계에서 위 왼쪽 아래 왼쪽

3단계에서 위 왼쪽 아래 왼쪽 아래 오른쪽 아래 왼쪽

이런식으로 움직인다.

이 움직임들 사이의 규칙을 찾아 낼 수  있다면 문제를 풀 수 있을 것 같다.

규칙 -> 그 전 단계의 것을 역순으로 시계 반대 방향으로 돌린것을 새롭게 붙이면 된다.

2단계의 역순 -> 왼쪽 아래 왼쪽 위

시계 반대 방향으로 회전 -> 아래 오른쪽 아래 왼쪽

2단계의 것 뒤에 새롭게 붙이면 3단계가 됨

-> 위 왼쪽 아래 왼쪽 + 아래 오른쪽 아래 왼쪽

규칙을 찾아 냈다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool map[101][101];
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1}; // 오, 위 , 왼, 아 순서
int t,x,y,d,g;
#define FOR(i,a,b) for(int i=a; i<b; i++)
inline bool is_in(int x,int y){ return x>=0 && x<=100 && y>=0 && y<=100;}

pair<int,int> check(int x,int y,int ori){
    int nx = x + dx[ori];
    int ny = y + dy[ori];
    if(is_in(nx,ny)) map[ny][nx] = true;
    return {nx,ny};
}

bool check_nemo(int x,int y){
  int dx[] = {0,1,0,1};
  int dy[] = {0,0,1,1};
  FOR(i,0,4){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(!is_in(nx,ny)) return false;
      if(!map[nx][ny]) return false;
  }
  return true;
}

void printmap(){
    cout<<endl;
    FOR(i,0,10){
        FOR(j,0,10){
            cout<<map[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

void printvector(vector<int> v){
    cout<<endl;
    FOR(i,0,v.size()){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

int main(){
    cin>>t;
    while(t--){
        cin>>x>>y>>d>>g;
        vector<int> v;
        v.push_back(d);
        FOR(i,0,g){
            vector<int> nv = v;
            reverse(nv.begin(),nv.end()); // 기존 벡터의 방향을 뒤집음.
            int size = nv.size();
            FOR(j,0,size){
                nv[j] = (nv[j] + 1) % 4;
                v.push_back(nv[j]);
            } //반시계 방향으로 회전 후 기존 벡터에 합체

        } //총 g번 실행된다.

        //들어 있는 화살표 대로 실행만 시키면 된다.
        map[y][x] = true;
        int size = v.size();
        FOR(i,0,size) {
            pair<int, int> np = check(x, y, v[i]);
            x = np.first;
            y = np.second;
        }
    }

    //드래곤 커브를 모두 돌리고 난 다음 사각형 체크
    int result = 0;
    FOR(i,0,101)
        FOR(j,0,101)
            result += check_nemo(i,j);
    cout<<result<<endl;

    return 0;
}

위에서 생각한 방법 그대로 구현을 해봤다. x좌표와 y좌표가 좌표계 기준으로 되어 있어서 행렬 기준으로 사용할때는 y와 x좌표를 반대로 집어 넣어 줘야 한다. 그리고 check()라는 함수가 이동한 다음 점을 찍는 함수기 때문에 맨 처음에 들어온 점을 체크해주는것을 실수했다.

이 2개의 실수 때문에 많은 삽질을 했다. x와 y좌표 변환을 조심하자.