백준(BOJ) 15685번 드래곤 커브

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

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

풀이 :

주어진 방향(d)을 집어넣는 배열을 만들고 세대가 지날때마다 배열을 통째로 복사하여 90도씩 돌려주고 다시 원래 배열에 집어 넣는 방식

으로 진행 하였다. 주의할점은 끝점에서 연결하여야 하니 다시 원래 배열에 집어 넣을때 끝부터 넣어주어야 한다.

코드 ( C++ )

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

const int MAX = 100 + 1;

int N;

int map[MAX][MAX];

bool visited[MAX][MAX];

int dy[4] = {0, -1, 0, 1};

int dx[4] = {1, 0, -1, 0};

bool InRange(int y, int x)

{

if (y >= 0 && x >= 0 && y < MAX && x < MAX)

return true;

return false;

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

cin >> N;

for(int i = 0; i < N; ++i)

{

int y, x, d, g;

cin >> x >> y >> d >> g;

visited[y][x] = true;

vector<int> direction;

//처음 방향 넣어준다.

direction.push_back(d);

for (int j = 0; j < g; ++j)

{

// direction배열 복사

vector<int> temp(direction);

// 끝부터 넣어준다.

for (int k = temp.size()-1; k >= 0; --k)

{

// 90 도 방향으로 회전하여 넣어준다.

direction.push_back((temp[k] + 1) % 4);

}

}

// 실제 방향대로 처음부터 이동하면서 visited 갱신

for (int i = 0; i < direction.size(); ++i)

{

int ny = y + dy[direction[i]];

int nx = x + dx[direction[i]];

if (InRange(ny, nx))

visited[ny][nx] = true;

y = ny;

x = nx;

}

}

// 1*1 정사각형 찾기

int cnt = 0;

for(int i=0; i<MAX; ++i)

for (int j = 0; j < MAX; ++j)

{

if (visited[i][j] && visited[i + 1][j] && visited[i][j + 1] && visited[i + 1][j + 1])

cnt++;

}

cout << cnt << "\n";

return 0;

}