728x90

드래곤 커브

 

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 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만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

  • 0: x좌표가 증가하는 방향 (→)
  • 1: y좌표가 감소하는 방향 (↑)
  • 2: x좌표가 감소하는 방향 (←)
  • 3: y좌표가 증가하는 방향 (↓)

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

예제 입력 1 

3
3 3 0 1
4 2 1 3
4 2 2 1

예제 출력 1 

4

예제 입력 2 

4
3 3 0 1
4 2 1 3
4 2 2 1
2 7 3 4

예제 출력 2 

11

예제 입력 3 

10
5 5 0 0
5 6 0 0
5 7 0 0
5 8 0 0
5 9 0 0
6 5 0 0
6 6 0 0
6 7 0 0
6 8 0 0
6 9 0 0

예제 출력 3 

8

예제 입력 4 

4
50 50 0 10
50 50 1 10
50 50 2 10
50 50 3 10

예제 출력 4 

1992

 

힌트
예제 1 예제 2
 

설명 

이런종류의 문제는 규칙을 찾아보자!

[ 0 = → , 1 = ↑ , 2 = ← , 3 = ↓ ]

세대       |   방향 정보

0               0

1               0  1

2               0  1  2  1

3               0  1  2  1  2  3  2  1

다음 세대의 추가되는 선분의 방향정보 = 이전 세대의 방향정보를 역순으로 탐색하면서 +1 % 4 를 한 것이 된다.

make_dragon_curve() 함수를 이용하여 map에 좌표를 찍어주고

count_square() 함수를 이용하여 좌표에 정사각형을 찾는다!

 

 

 

소스코드

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
#include <iostream>
#include <vector>
#define MAX 101
using namespace std;
int n, x, y, g, d, ans;
vector<int> dir;
int map[MAX][MAX];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, -1, 0, 1 };
void make_dragon_curve()
{
    int size = dir.size();
    for (int i = size - 1; i >= 0; i--)
    {
        int next_d = (dir[i] + 1) % 4;
        x += dx[next_d];
        y += dy[next_d];
        map[y][x] = 1;
        dir.push_back(next_d);
    }
}
void count_square()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            if (map[i][j]==1 && map[i][j + 1] == 1 && map[i + 1][j] == 1 && map[i + 1][j + 1]==1)
                ans++;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y >> d >> g;
 
        dir.clear();
 
        map[y][x] = 1;
        x += dx[d];
        y += dy[d];
        map[y][x] = 1;
        dir.push_back(d);
        for (int j = 0; j < g; j++)
        {
            make_dragon_curve();
        }
    }
    count_square();
    cout << ans;
    return 0;
}
 cs

https://yabmoons.tistory.com/60

 

[ 백준 15685 ] 드래곤 커브 (C++)

백준의 드래곤커브(15685) 문제이다. ( 문제 바로가기 ) 삼성의 SW역량테스트 기출문제이다. [ 문제풀이 ] 1. 그냥 문제를 보면 무슨소린지도 잘 모르겠고, 드래곤커브가 뭔지도 잘 모르겠다 사실.

yabmoons.tistory.com

참고하였습니다. 감사합니다.~

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Level2 프로그래머스] 문자열 압축  (0) 2021.09.24
[구현 BOJ-16234] 인구 이동, c++  (0) 2021.08.10
[구현, BOJ-15684] 사다리 조작, c++  (1) 2021.08.09
[시뮬레이션, BOJ-15683]감시, c++  (0) 2021.06.04
[구현, BOJ-14891] 톱니바퀴, c++  (0) 2021.05.25
728x90

뱀

문제

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데,  정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

삼성 SW 기출문제 3번째 문제 "뱀" 이라는 문제이다

queue 를 이용하여 {y,x}를 집어 넣어주었고

종료 조건으로 1. 몸통을 만났을때, 2. 벽을 만났을때 이렇게 설정하였다.

코드가 좀 지저분해서 고치고 싶은데 고칠시간에 한문제 더 푸는게 좋을거 같아서 여기서 끝.

아, 중간에 map을 print해가면서 초 단위로 움직임을 직접 보면서 디버깅하니까 좋았다.

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, l, ans;
int map[101][101];
//움직임을 담는 vector (sec, dir)
vector<pair<int, char>> moves;
//뱀의 좌표를 담는 queue (y, x)
queue<pair<int, int>> q;
//우, 좌, 하, 상
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
 
bool move(int y, int x)
{
    //1. 범위안에 있고
    if (y >= 1 && x >= 1 && y <= n && x <= n)
    {
        //2. 앞에 사과가 있을때
        if (map[y][x] == 2)
        {
            map[y][x] = 1;
            q.push({ y,x });
            ans++;
            return true;
        }
        //3. 아무것도 없을때
        else if (map[y][x] == 0)
        {
            map[y][x] = 1;
            q.push({ y,x });
            int fy = q.front().first;
            int fx = q.front().second;
            q.pop();
            map[fy][fx] = 0;
            ans++;
            return true;
        }
        //4. 자기 자신이 있을때
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}
void bfs(int y, int x)
{
    q.push({ y,x });
    map[y][x] = 1;
    int dir = 0;
    while (true)
    {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        
        if (move(ny,nx))
        {
            /*
            cout << endl;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    cout << map[i][j] << ' ';
                }
                cout << endl;
            }
            cout << endl;
            */
            y = ny; x = nx;
            if (moves.size() > 0)
            {
                for (int i = 0; i < moves.size(); i++)
                    moves[i].first--;
 
                if (moves[0].first == 0)
                {
                    switch (dir)
                    {
                    case 0:
                        if (moves[0].second == 'D')
                            dir = 2;
                        else
                            dir = 3;
                        break;
                    case 1:
                        if (moves[0].second == 'D')
                            dir = 3;
                        else
                            dir = 2;
                        break;
                    case 2:
                        if (moves[0].second == 'D')
                            dir = 1;
                        else
                            dir = 0;
                        break;
                    case 3:
                        if (moves[0].second == 'D')
                            dir = 0;
                        else
                            dir = 1;
                        break;
                    }
                    moves.erase(moves.begin());
                }
            }
        }
        else
        {
            return;
        }
    }
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        int y, x;
        cin >> y >> x;
        map[y][x] = 2;
    }
    cin >> l;
    for (int i = 0; i < l; i++)
    {
        int a; char b;
        cin >> a >> b;
        moves.push_back({ a,b });
    }
    sort(moves.begin(), moves.end());
    bfs(1, 1);
    cout << ans + 1;
    return 0;
}
 cs

www.acmicpc.net/problem/3190

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[simulation, BOJ-14499] 주사위 굴리기, c+  (0) 2021.05.12
[mathmatics BOJ-13458] 시험감독, c++  (1) 2021.05.11
[Simulation, BOJ-12100] 2048(Easy), c++  (0) 2021.05.10
[graph theory, BOJ-13460] 구슬 탈출2, c++  (0) 2021.05.09
[graph theory, BOJ-1197] 최소 스패닝 트리, c++  (0) 2021.05.06

+ Recent posts

티스토리툴바