백준 15685 드래곤 커브

작성일 | In |

Problem : 드래곤 커브

유형 : 구현

문제, 예제 입출력 설명

그림이 많아 링크로 대체합니다

해결 전략

커브가 움직인 위치는, 좌표로 표시할 수 있다.
드래곤 커브의 다음 세대는, 이전 세대의 영향을 받는다.
90도씩 돌아간뒤, 끝점에 이어붙이는것은 이전에 움직인 것에서의 역방향인걸 알 수 있다.

좀더 자세히 이야기를 해보자면

  • 오른쪽 방향을 90도 돌린다면
  • 아래쪽 방향이 될것이다.
  • 하지만, 그것을 우측 방향으로 이동한것의 끝에 이어 붙이면
  • 끝을 기준으로는 아래쪽 이 아니라 위쪽으로 진행한다는 것을 알 수 있다.

이전에 이동 방향이 0이었다면,
다음에 이동할 방향은
이동을 완료한 위치에서 “이전에 이동한 방향의 다음 방향이다”
즉 0방향으로 움직인 곳부터, 1방향으로 움직인다.

만약
총 0 1 방향으로 움직였다면, 다음에 움직이는 경로는
0 1 방향으로 움직이고 이동을 마친 위치부터
2 1 방향으로 움직인다.

왜
2 1 이냐면
(0 1)
1 에서 다음 방향인 2 이고
0 에서 다음 방향인 1 이다.

돌린 다음. 끝 부분에 붙이는 것이기 때문에 가장 마지막에 이동한 방향 에 영향 받으므로
역순으로 탐색해야 한다.

그 다음 세대는

0 1 2 1 이었으니
2 3 2 1 이 된다.

주의할 점

  • 이동 했던 방향을 보관하고 있는 vector 에 새로운 방향을 추가할때 주의해야한다.
  • 처음에 지금까지 이동 방향이 몇개 있는지를 미리 찾아두고
  • 담겨있는 방향을 역순으로 탐색하면서, 새로운 방향을 추가해야한다.
    • 이때 추가된 새로운 방향들은, 다음 세대 드래곤 커브때 이용된다.
    • 즉, 현재 진행하고 있는 과정에는 필요가 없으므로 지금까지의 이동방향을 미리 찾아둔 것이다

풀이

드래곤 커브 첫세대를 관리한다

  • 시작점을 표시하고
  • 방향에 맞춰 이동한뒤 해당 지점에도 표시한다
  • 그리고, 이동방향을 벡터에 넣어둔다.

드래곤 커브를 진행한다

  • 현재 들어가있는 방향의 개수를 미리 세어두고
  • 방향의 개수만큼, 역방향 으로 찾아간다 가장 마지막에 이동한 방향부터 탐색
    • 이전 방향에 따라서, 이어서 뻗어나갈 다음 방향의 좌표를 구한다

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

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

int curv_n;
bool board[102][102];

int x, y;
int level;
vector<int> vec;

bool square_check(int i, int ii) {
    for (int x = i; x < i + 2; ++x) {
        for (int y = ii; y < ii + 2; ++y) {
            if (board[x][y] == false) return false;
        }
    }
    return true;
}

void get_answer() {
    int answer = 0;
    for (int i = 0; i <= 100; ++i) {
        for (int ii = 0; ii <= 100; ++ii) {
            if (square_check(i, ii)) answer++;
        }
    }
    cout << answer << "\n";
}

void move(int dir) {
    x += dx[dir];
    y += dy[dir];
    board[x][y] = true;
    vec.push_back(dir);
}

void solve() {
	for (int i = 1; i <= level; ++i) {
		int vec_size = vec.size();
		for (int k = vec_size; k >= 1; --k) {
			int dir = (vec[k - 1] + 1) % 4;
			move(dir);
		}
	}
}

void init(int dir) {
    vec.clear();
    board[x][y] = true;
    move(dir);
}

void input() {
    cin >> curv_n;
    int dir;
    while (curv_n--) {
        cin >> y >> x >> dir >> level;
        init(dir);
        solve();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    input();
    get_answer();

    return 0;
}

피드백

연관 관계를 찾고, 변경되어지는 규칙을 찾아보자