[algorithm] 백준 - 드래곤 커브

이 문제는 삼성 SW 기출 문제이고, simulation 문제이다.

 

1. 시작 점 (x, y)

2. 시작 방향 (direction)

 

struct point{
    int x,y,direction;
};

 

n세대는 n - 1 세대 드래곤 커브 끝점을 기준으로 시계 방향으로 90도 회전시킨다음 끝점에 붙인 것이다.

그렇다면 점들의 위치는 어떤 방식으로 정해지는 건지 궁금하여 점이 변하는 방향을 따져봤다.

 

0: x좌표가 증가하는 방향 (→)

1: y좌표가 감소하는 방향 (↑)

2: x좌표가 감소하는 방향 (←)

3: y좌표가 증가하는 방향 (↓)

 

pair<int,int> direct[]={{1,0},{0,-1},{-1,0},{0,1}};

 

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

 

각 세대를 살펴봤을 때, 회전 방향은 n - 1 세대의 회전방향을 역순으로 아래와 같이 회전한다는 것을 알 수 있다.

 

 

int rotationDirect[]={1,2,3,0};

 

따라서 회전할 때 역순으로 탐색하여 회전 방향을 설정 후 벡터에 저장하고,

벡터에 저장하기 전 벡터의 사이즈를 시작점으로 하여

순차적으로 탐색하면서 바로 전 정점에 대해 해당 회전 방향을 더하고

해당 정점에 대한 방문 여부를 체크한다.

그리고 세대가 증가 함에 따라 위를 반복한다.

 

void upgradeGeneration(point p, int generation){
    int pgeneration = 0;
    vector<point> pointVector;
    point end;
    end.x = p.x + direct[p.direction].first;
    end.y = p.y + direct[p.direction].second;
    end.direction = p.direction;
    visitedPoint[end.x][end.y] = true;
    pointVector.push_back(end);
    while(pgeneration != generation){
        int size = pointVector.size();
        pgeneration++;
        for(int i = size - 1; i >= 0; i--){
            end.direction = rotationDirect[pointVector[i].direction];
            pointVector.push_back(end);
        }
        for(int i = size; i < pointVector.size(); i++){
            pointVector[i].x = pointVector[i - 1].x + direct[pointVector[i].direction].first;
            pointVector[i].y = pointVector[i - 1].y + direct[pointVector[i].direction].second;
            visitedPoint[pointVector[i].x][pointVector[i].y] = true;
        }
    }
}

 

그 후 체크된 방문 배열에 대해 정사각형인지 확인 후 정사각형이라면 answer를 증가시킨다.

 

void checkSquare(){
    for(int i = 0; i < 101; i++){
        for(int j = 0; j < 101; j++){
            if(visitedPoint[i][j] == true && visitedPoint[i + 1][j + 1] == true && visitedPoint[i+1][j] == true && visitedPoint[i][j + 1] == true){
                answer++;
            }
        }
    }
}

 

전체 코드는 이렇다.

 

//드래곤 커브
#include <iostream>
#include <vector>
using namespace std;

struct point{
    int x,y,direction;
};
pair<int,int> direct[]={{1,0},{0,-1},{-1,0},{0,1}};
int rotationDirect[]={1,2,3,0};
bool visitedPoint[102][102];
int answer = 0;
void upgradeGeneration(point p, int generation){
    int pgeneration = 0;
    vector<point> pointVector;
    point end;
    end.x = p.x + direct[p.direction].first;
    end.y = p.y + direct[p.direction].second;
    end.direction = p.direction;
    visitedPoint[end.x][end.y] = true;
    pointVector.push_back(end);
    while(pgeneration != generation){
        int size = pointVector.size();
        pgeneration++;
        for(int i = size - 1; i >= 0; i--){
            end.direction = rotationDirect[pointVector[i].direction];
            pointVector.push_back(end);
        }
        for(int i = size; i < pointVector.size(); i++){
            pointVector[i].x = pointVector[i - 1].x + direct[pointVector[i].direction].first;
            pointVector[i].y = pointVector[i - 1].y + direct[pointVector[i].direction].second;
            visitedPoint[pointVector[i].x][pointVector[i].y] = true;
        }
    }
}
void checkSquare(){
    for(int i = 0; i < 101; i++){
        for(int j = 0; j < 101; j++){
            if(visitedPoint[i][j] == true && visitedPoint[i + 1][j + 1] == true && visitedPoint[i+1][j] == true && visitedPoint[i][j + 1] == true){
                answer++;
            }
        }
    }
}
int main(void){
    int num;
    cin >> num;
    for(int i = 0; i < num; i++){
        point p;
        int generation;
        cin >> p.x >> p.y >> p.direction >> generation;
        visitedPoint[p.x][p.y] = true;
        upgradeGeneration(p,generation);
    }
    checkSquare();
    cout << answer;
}