백준 15685 드래곤 커브 C++

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

15685번: 드래곤 커브

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ15685.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ15685
//
//  Created by 최화연 on 2022/04/21.
//

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

int N;
int board[102][102] = {0, };
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

deque<int> curve;
int answer = 0;


int main(int argc, const char * argv[]) {
    cin >> N;
    for (int i=0; i<N; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        
        curve.push_back(d);
        for (int j=0; j<g; j++) {
            int idx = curve.size()-1;
            for (int k=idx; k>=0; k--) {
                curve.push_back((curve[k]+1)%4);
            }
        }
        
        board[y][x] ++;
        for (int j=0; j<curve.size(); j++) {
            x += dx[curve[j]];
            y += dy[curve[j]];
            board[y][x] ++;
        }
        curve.clear();
    }
    
    for (int y=0; y<=100; y++) {
        for (int x=0; x<=100; x++) {
            if (board[y][x] > 0 && board[y][x+1] > 0 && board[y+1][x] > 0 && board[y+1][x+1] > 0) {
                answer ++;
            }
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

---

풀이 과정

풀이 시간 35분

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

int N;
int board[102][102] = {0, };
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

deque<int> curve;
int answer = 0;


int main(int argc, const char * argv[]) {
    cin >> N;
    for (int i=0; i<N; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        
        curve.push_back(d);
        for (int j=0; j<g; j++) {
            int idx = curve.size()-1;
            for (int k=idx; k>=0; k--) {
                curve.push_back((curve[k]+1)%4);
            }
        }
        
        board[y][x] ++;
        for (int j=0; j<curve.size(); j++) {
            x += dx[curve[j]];
            y += dy[curve[j]];
            board[y][x] ++;
        }
        curve.clear();
    }
    
    for (int y=0; y<=100; y++) {
        for (int x=0; x<=100; x++) {
            if (board[y][x] > 0 && board[y][x+1] > 0 && board[y+1][x] > 0 && board[y+1][x+1] > 0) {
                answer ++;
            }
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

---

이전 풀이

드래곤 커브를 구성해 나가는데 회전변환과 평행이동 공식을 이용해서 문제를 해결하였다.

드래곤 커브의 끝점을 기준으로 이전 점들을 90도 시계방향으로 회전시켜서 생긴 새로운 점을 생성해나가면 된다.

 

1. 드래곤 커브의 끝점이 기준이기 때문에, 원점에 대한 회전 변환 공식을 활용하기 위해 드래곤 커브의 끝점을 원점으로 만들기 위해 평행이동을 한다.

즉, 드래곤 커브의 끝점 (x, y) = (a, b)인 경우 x축으로 -a만큼 y축으로 -b만큼 드래곤 커브의 점을 평행 이동한다.

드래곤 커브의 임의의 점을 평행 이동하면 (x, y) = (c, d) -> (c-a, d-b)가 된다.

 

2. 평행 이동한 점을 회전 변환한다. 

https://ko.wikipedia.org/wiki/회전변환행렬

회전변환행렬 - 위키백과, 우리 모두의 백과사전

 회전변환 공식은 원점을 기준으로 반시계 방향으로 임의의 점 (x, y)를 특정 각도만큼 회전한 후의 점 (x, y)를 구하는 공식이다.

이 공식을 적용하는데 굉장히 헷갈렸다.

드래곤 커브는 끝점을 기준으로 시계방향으로 90도 회전한 점을 구해야하기 때문에, 회전 변환한 공식에 회전 각을 270도로 설정하여 구하면 되지 않을까?라고 생각했는데 아니었다..!

 왜냐하면, 회전변환을 나타내는 좌표평면 상에서 y축은 원점을 기준으로 위에 있으면 +값을, 아래에 있으면 -값을 가진다.

하지만, 드래곤 커브 문제에서 격자판은 0 <= x,y <= 100이므로 특정 점을 기준으로 위에 있으면 -값을, 아래에 있으면 +값을 가진다.

따라서, 회전변환 공식에서 y축을 뒤집어 생각해야한다는 것이다. 그렇다면 결국 90도 회전하는 회전 변환을 하면 된다!!

sin90º = 1, cos90º = 0

x' = xcos90º - ysin90º = -y

y' = xsin90º -  ycos90º = x

즉, (x, y) -> (x', y')로 90도 회전이동을 하면 (x', y') -> (-y, x)이다.

 

3. 2.과정은 원점에 대한 회전이동을 했기 때문에 끝점을 기준으로 하기 위해 x축으로 a만큼, x축으로 b만큼 평행이동을 한다.

 

//
//  main.cpp
//  BJ15685
//
//  Created by Hwayeon on 2021/08/12.
//

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

int N;
//드래곤 커브의 위치들을 담을 벡터
vector<pair<int, int>> dragon_curve;

//격자 기준이 아닌 칸을 기준으로 해주기 위해 칸을 하나 더 할당한 102x102로 한다
int board[102][102] = {0,};

//0->우, 1->상, 2-> 좌, 3->하
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

void make_dragon_curve(int g){
    while(g > 0){
    	//드래곤 커브의 끝점의 위치를 lx, ly에 초기화, 현재 dragon_curve의 사이즈로 d_size를 초기화
        int lx = dragon_curve.back().first;
        int ly = dragon_curve.back().second;
        int d_size = dragon_curve.size();
        //드래곤 커브의 끝점의 이전 점부터 시작 점까지의 위치를 끝점을 기준으로 회전 변환하여 드레곤 커브를 만든다
        for(int i=d_size-2; i>=0; i--){
            //평행이동
            int x = dragon_curve[i].first - lx;
            int y = dragon_curve[i].second - ly;
            //회전변환 후 평행이동
            int nx = -y + lx;
            int ny = x + ly;
            dragon_curve.push_back({nx, ny});
            board[ny][nx] = 1;
        }
        g--;
    }
}

int cal_area(){
    int area = 0;
    for(int i=0; i<101; i++){
        for(int j=0; j<101; j++){
        	//해당 위치를 기준으로 4칸을 확인하여 모두 드래곤 커브를 구성하는 칸이라면 카운팅
            if(board[i][j] && board[i][j+1] && board[i+1][j] && board[i+1][j+1]) area++;
        }
    }
    return area;
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N; i++){
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        //0세대 드래곤 커브를 만든다 -> dragon_curve에 위치 추가, board 값 1로 변경
        dragon_curve.clear();
        dragon_curve.push_back(make_pair(x, y));
        board[y][x] = 1;
        dragon_curve.push_back(make_pair(x+dx[d], y+dy[d]));
        board[y+dy[d]][x+dx[d]] = 1;
        //g세대 드래곤 커브를 만든다 
        make_dragon_curve(g);
    }
    cout << cal_area() << endl;
    return 0;
}
//시간복잡도 = T(N*g*dragon_curve.size() + 100*100), 공간복잡도 = O(n^2)
//최악의 경우 -> N=20, g=10, dragon_curve.size() = 1025(10세대인 경우) -> 215000번 연산