[백준 / c++] 15685 드래곤커브

 

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

15685번: 드래곤 커브

문제요약

주어진 알고리즘 대로 격자내에 드래곤 커브를 그린다. 격자내에서 드래곤 커브에 둘러쌓인 1x1 사각형이 모두 몇개인지 출력한다. 

문제해결

새로 생기는 드래곤 커브들의 방향을 결정할 때, 이전에 생겼던 커브를 가장 최근에 생긴 순서대로 읽으면서, 그 커브의 방향에 +1을 하면 새로운 커브들의 방향이 결정된다. 
이를 스택을 이용하여 풀었다.

코드

#include <iostream>
#include <vector>

using namespace std;
         // 0   1   2   3
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int grid[101][101] = {};
int N;

int next_dir(int current){
    if(current == 4) return 0;
    else return current + 1;
}

int main(){
    cin >> N;

    for(int i=0; i<N; i++){
        // cout << i <<"==========\n"<< endl;
        int x, y, d, G;
        cin >> x >> y >> d >> G;
        
        grid[y][x] = 1;

        int g = 0;
        x += dx[d];
        y += dy[d];
        grid[y][x] = 1;
        vector<int> directions = {d+1 == 4 ? 0 : d+1};
        g++;

        while(g <= G){
            // cout<<"gen :"<<g<<endl;
            int num_dir = directions.size();

            for(int n=num_dir-1; n>=0; n--){
                auto dir = directions[n];

                x += dx[dir];
                y += dy[dir];
                
                // cout << "(" << x << ", " << y << "), ";
                if(x<0 || x>100 || y<0 || y>100){
                    return 0;
                }

                grid[y][x] = 1;

                directions.push_back(dir+1 == 4 ? 0 : dir+1);
            }
            g++;
            // cout<<endl;
        }
    }

    int sq_i[4] = {0, 1, 0, 1};
    int sq_j[4] = {0, 0, 1, 1};
    int ans = 0;
    for(int i=0; i<100; i++){
        for(int j=0; j<100; j++){

            int count = 0;
            for(int n=0; n<4; n++){
                if(grid[i+sq_i[n]][j+sq_j[n]]) count++;
            }
            if(count == 4) ans++;
        }
    }
    
    cout << ans;

}