[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만 유효한 좌표이다.

 

문제접근법.

1. 90도로 돌릴 때, 방향(0, 1, 2, 3)에 대해서 일대일 관계가 이루어진다.

2. 새로 붙어지는 드래곤 커브는, 기존의 커브에서 가장 마지막에 있는 방향부터 90도로 돌아가기 시작한다.

 

드래곤커브를 직접 생성하기 위한 코드를 작성해야 한다. 방향을 저장하는 자료구조를 사용하고, 생성된 드래곤 커브를 Check배열에 저장해서 정사각형을 몇 개인지 확인한다.

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
int x, y, d, g;
int N;
int op[4][2] = { {0,1},{-1,0}, {0,-1},{1,0} };
int check[101][101] = { 0 };
int answer = 0;
vector<int> v;
 
int main(void) {
    freopen("input.txt", "r", stdin);
    memset(check, 0, sizeof(check));
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> y >> x >> d >> g;
        v.clear();
 
        int o_x = x;
        int o_y = y;
        check[o_x][o_y] = 1;
 
        v.push_back(d);
        for (int j = 1; j <= g; j++) {
            int len = v.size() - 1;
            for (int k = len; k >= 0; k--) {
                int n_d = (v.at(k) + 1) % 4;
                v.push_back(n_d);
            }
        }
 
        for (int j = 0; j < v.size(); j++) {
            o_x += op[v.at(j)][0];
            o_y += op[v.at(j)][1];
 
            check[o_x][o_y] = 1;
        }
    }
 
    // CHECK 
    for (int i = 0; i <= 99; i++) {
        for (int j = 0; j <= 99; j++) {
            if (check[i][j] == 1 && check[i + 1][j] == 1 && check[i][j + 1] == 1 && check[i + 1][j + 1] == 1)
                answer += 1;
        }
    }
 
    cout << answer << endl;
    return 0;
}