백준 15685. 드래곤 커브 (구현)

 

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

15685번: 드래곤 커브

현재까지 찾은 좌표들을 끝점을 기준으로 90도 돌리는 좌표를 찾음으로써 문제를 풀었다.

(다른 풀이들을 보니까 드래곤 커브에 규칙이 있는 거 같다. )

 

*이 문제에서는 x로 받는 값이 가로값, y로 받는값이 세로값이다. 

하지만 나는 문제 풀때 x를 세로값, y를 가로값으로 설정했고, 이문제 풀이에서도 그렇게 설명하겠다. 

 

1. 구현 포인트

1) 한 좌표를 끝점을 기준으로 시계방향으로 90도 회전한 좌표를 생성한다. 

(이 방법을 쓰려면 g가 0일때는 예외적으로 처리해주어야한다. ) g가 0인 경우 -> 인풋값 d를 보고 새로운 좌표값을 vector에 저장하고, 끝점을 새로운 좌표값으로 업데이트 해줌.

if(k == 0) // 0세대일때
{
    nx = x + dx[d]; // d에 입력된 인풋을 보고 좌표를 찾음
    ny = y + dy[d];
    _vec.push_back(make_pair(nx, ny)); // 현재까지 그려진 좌표값을 담음
    board[nx][ny] = 1;
    enx = nx;
    eny = ny;
}

1-1) 끝점기준으로 시계방향 90도 회전 

 

검정색점 (1, 4)를 끝점 (2, 2)에 대해 90도 시계방향을 회전한다고 했을 때 이를 코드로 작성하면 아래와같다. 

//enx, eny: 끝 점의 x, y 값
//x, y: 현재 옮기려는 점의 x, y값
//nx, ny: 옮겨진 점의 x, y값

int dx = x - enx; // 점과 끝점의 세로값 차이 -> 옮기려는 점의 y값에 영향을 줌
int dy = y - eny; // 점과 끝점의 가로값 차이 -> 옮기려는 점의 x값에 영향을 줌

int nx = enx + dy 
int ny = eny - dx;

_vec.push_back(make_pair(nx, ny)); // 현재까지 그려진 좌표를 담음
board[nx][ny] = 1;

 

1-2) g값이 증가할 때마다, 끝점 업데이트한다.

g가 0인 경우를 제외하고, 끝점은 항상 인풋으로 받았던 x, y가 g번 회전을 거쳐 만들어진 좌표이다. 
따라서 enx와 eny는 첫번째 좌표를 회전한 값으로 업데이트 하면된다. 

 

for(int k = 0; k <= g; k++)
{
    if(k == 0) // 0세대일때
    {
        nx = x + dx[d];
        ny = y + dy[d];
        _vec.push_back(make_pair(nx, ny));
        board[nx][ny] = 1;
        enx = nx;
        eny = ny;
    }
    else
    {
        int ss = _vec.size();
        for(int j = 0; j < ss; j++)
        {
            ddx = _vec[j].first - enx;
            ddy = _vec[j].second - eny;
            nx = enx + ddy;
            ny = eny - ddx;
            if(j == 0) // 입력으로 받은 좌표값을 회전 시켜 얻은 nx, ny를 새로운 enx, eny로 업데이트
            {
                tenx = nx; 
                teny = ny;
            }
            _vec.push_back(make_pair(nx, ny)); 
            board[nx][ny] = 1;
        }
        enx = tenx;
        eny = teny;

    }

}

 

2) 네 꼭짓점이 모두 드래콘 커브의 일부인 1x1 사각형을 판별한다. 

현재 드래곤 커브로 방문한 좌표(i, j)를 board[i][j] = 1로 설정해주어,

(i, j) (i, j+1), (i+1, j), (i+1, j+1)이 모두 1이면 사각형이라고 판정했다. 

 

 

코드는 아래와 같다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int n;

int dx[4] = {0,-1,0,1};
int dy[4] = {1,0,-1,0};
int board[102][102];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    int x, y, d, g;
    int nx, ny; //nx, ny: 옮겨진 점의 x, y값
    int enx, eny; //enx, eny: 끝 점의 x, y 값
    int ddx, ddy;
    int tenx, teny;
    for(int i = 0; i < n; i++)
    {
        cin >> y >> x >> d >> g;
        board[x][y] = 1;
        vector<pair<int, int>> _vec; // 현재까지 그려진 좌표를 담음
        _vec.push_back(make_pair(x, y));
        for(int k = 0; k <= g; k++)
        {
            if(k == 0) // 0세대일때
            {
                nx = x + dx[d];
                ny = y + dy[d];
                _vec.push_back(make_pair(nx, ny));
                board[nx][ny] = 1;
                enx = nx;
                eny = ny;
            }
            else
            {
                int ss = _vec.size();
                for(int j = 0; j < ss; j++)
                { 
                    ddx = _vec[j].first - enx; // 점과 끝점의 세로값 차이 -> 옮기려는 점의 y값에 영향을 줌
                    ddy = _vec[j].second - eny; // 점과 끝점의 가로값 차이 -> 옮기려는 점의 x값에 영향을 줌
                    nx = enx + ddy;
                    ny = eny - ddx;
                    if(j == 0) // 입력으로 받은 좌표값을 회전 시켜 얻은 nx, ny를 새로운 enx, eny로 업데이트
                    {
                        tenx = nx;
                        teny = ny;
                    }
                    _vec.push_back(make_pair(nx, ny));
                    board[nx][ny] = 1;
                }
                enx = tenx;
                eny = teny;
  
            }

        }
        

    }
    int ans = 0;
    for(int i = 0; i < 101; i++)
    {
        for(int j = 0; j < 101; j++)
        {
            if(board[i][j] == 1 && board[i][j+1] && board[i+1][j] && board[i+1][j+1])
            {
                ans++;
            }
        }
    }

    cout << ans;


}