[BOJ] 15685. 드래곤 커브

#include<iostream>
#include<vector>
using namespace std;

/*
 다음과 같은 순서로 진행된다.
 →(0)  ↑(1)  ←(2)  ↓(3)
 > 모양이 끝점이라 생각하자.
 (st)---->(end) 이 모양에서 90도 회전하면
 끝점을 기준으로 회전이 이뤄지므로 (문제 조건)
 (end)점이 (st)점이 되고 ↓ 같은 모양을 갖게 된다.
 */
int dir[] = {0,1,2,3};

// 동 북 서 남
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

int map[101][101];

int n,m,d,g;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    /*
     TC 2
     2 7 3 4를 보자
     다음과 같이 진행됨을 알 수 있다.
     0세대 남
     1세대 동
     2세대 북 [동](=1세대)
     3세대 북 서 [북 동](=2세대)
     4세대 북 서 남 서 [북 서 북 동](=3세대)
     */
    int tc;
    cin >> tc;
    for(int i=0; i<tc; i++){
        vector<int> v;
        cin >> m >> n >> d >> g;
        map[n][m] = 1;
        
        // 0세대
        n += dx[d];
        m += dy[d];
        map[n][m] = 1;
        
        // 1세대
        if( g > 0 ){
            n += dx[(d+1) % 4];
            m += dy[(d+1) % 4];
            map[n][m] = 1;
            v.push_back((d+1) % 4);
        }
        
        if( g > 1 ){
            for(int j=2; j<=g; j++){
                int size = (int) v.size();
                for(int k=0; k<size; k++){
                    /*
                     기존 vector에 insert되면
                     인덱스는 2배씩 점프한다.
                     [ 1 2 ]가 있는데
                     처음엔 1를 가리키기위해
                     0번째 인덱스를 참조하고
                     0이란 값이 insert가 되면
                     [ 0 1 2 ]가 된다.
                     여기서 2를 가리키기 위해선 2번째 인덱스를 참조해야한다.
                     */
                    int p = k * 2;
                    int idx = ( v[p] + 1 ) % 4;
                    /*
                     [ 2,7,3,4 ]라고 입력이 주어진다면
                     (실제로 들어오는 입력은 7,2,3,4 이지만 x,y 순서를 바꿨다.)
                     2,7에서 시작하여
                     방향은 3(=남)이고
                     세대는 4세대까지 진행되며
                     여기서 3,4세대의 진행 방향은 다음과 같다.
                     
                     3세대 북 서 [북 동](=2세대)
                     4세대 북 서 남 서 [북 서 북 동](=3세대)
                     
                     여기서 4세대를 반으로 나누어 관계를 찾아보면
                     (1) 북 서 남 서 / (2) 북 서 북 동
                     (2)의 '북'에서 한 방향 회전한 결과는 (1)의 마지막 값(=서)이다.
                     (2)의 '서'에서 한 방향 회전한 결과는 (1)의 세번째 값(=남)이다.
                     (2)의 '북'에서 한 방향 회전한 결과는 (1)의 두번째 값(=서)이다.
                     (2)의 '동'에서 한 방향 회전한 결과는 (1)의 세번째 값(=북)이다.
                     
                     그렇기 때문에 기존의 vector값(=이전 세대)에서
                     i 번째 인덱스 값을 회전 시킨 값을
                     vector에 처음에 insert를 해주게 되는 작업을 반복하면
                     최종적으로 원하는 순서대로 vector값을 갖게 된다.
                     */
                    v.insert(v.begin(), idx);
                } // end of for k
                
                /*
                 이전 세대 끝점을 기준으로
                 현재 vector에 들어있는 방향대로
                 방문 정점에 표시를 해준다.
                 */
                for(int k=0; k < size*2; k++){
                    n += dx[ v[k] ];
                    m += dy[ v[k] ];
                    map[n][m] = 1;
                } // end of for k
                
            } // end of for j
            
        } // end of if
    } // end of for i
    
    int ans = 0;
    for(int i=1; i<101; i++){
        for(int j=1; j<101; j++){
            /*
             네 꼭짓점이 모두 1이라면 드래곤 커브의 일부이다.
             */
            if( map[i][j] == 1 && map[i-1][j] == 1 &&
               map[i][j-1] == 1 && map[i-1][j-1] == 1
               ){
                ans ++;
            }
        } // end of for j
    } // end of for i
    
    cout << ans << endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//시간 복잡도: O(n*2^g + xy)
//공간 복잡도: O(xy)
//사용한 알고리즘: 반복문
//사용한 자료구조: 스택(1차원 벡터), 2차원 배열, 1차원 배열

bool map[102][102];

//끝점의 정보
int end_x = 0;
int end_y = 0;


//왼쪽, 위쪽, 오른쪽, 아래쪽
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};


//이전 세대의 방향정보를 저장하는 스택
//stl 스택쓰면 귀찮으니까 인덱스로 접근 할 수 있는 벡터를 사용한다.
vector<int> dragon;

//스택을 조사하면서 드래곤 커브를 만드는 함수
void make_generation(vector<int> &dragon){
    
    //현재 스택의 크기를 먼저 계산해 놓는다.
    int size = (int)dragon.size();
    
    //스택의 뒤에서 부터 꺼내면서
    //다음세대의 방향정보를 dir = (dragon[i] + 1)%4; 규칙에 따라 생성한다.
    for(int i=size-1; i>=0; i--){
        int dir = (dragon[i] + 1)%4;
        
        //다음 세대의 방향정보를 바탕으로 다음 x,y를 찾고 이를 갱신한다.
        end_x = end_x + dx[dir];
        end_y = end_y + dy[dir];
        
        //만들어진 드래곤 커브를 지도에 놓아준다.
        map[end_x][end_y] = true;
        
        //다음세대를 위하 스택에 방향정보를 넣어준다.
        dragon.push_back(dir);
    }
}

int main(){
    
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        //x, y의 순서를 바꿔서 입력받는다.
        int y, x, d, g;
        cin >> y >> x >> d >> g;
        
        //기존 드래곤 커브의 스택을 비워준다.
        dragon.clear();
        
        //끝점을 갱신한다.
        end_x = x;
        end_y = y;
        
        //현재 위치에 드래곤 커브가 놓여있으므로 지도에 표시해준다.
        map[end_x][end_y] = true;
        
        //0세대는 미리 만들어 놓는다.
        end_x = x + dx[d];
        end_y = y + dy[d];
        
        //0세대를 만든 이후에도 지도에 표시해준다.
        map[end_x][end_y] = true;
        
        //0세대의 방향정보를 스택에 넣어준다.
        dragon.push_back(d);
        
        //반복문을 통해 0부터 차례차례 드래곤 커브를 만들면서 g세대까지 만든다.
        for(int i=0; i<g; i++){
            
            //드래곤 커브를 만들자
            make_generation(dragon);
        }
        
    }
    
    //100*100 2차원 행렬을 2중 for문 사용한 단순한 탐색
    //인접한 4칸이 모두 true이면, 4칸이 모두 드래곤 커브의 일부인것
    //갯수를 1증가시킨다.
    int result = 0;
    for(int i=0; i<=100; i++){
        for(int j=0; j<=100; j++){
            
            //인접한 4칸의 정사각형이 모두 드래곤의 일부이면
            if(map[i][j] == true && map[i][j+1] == true && map[i+1][j] == true && map[i+1][j+1] == true){
                
                //갯수를 1 증가시킨다.
                result++;
            }
        }
    }
    
    //갯수 출력
    cout << result << endl;   
}