## SW 역량테스트 - [백준] 드래곤 커브 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

### SW 역량테스트 - [백준] 드래곤 커브 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 10. 15. 23:43

## SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

### 해답 코드 :

``````#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int map[101][101] = { false };
int N;
int ans;

typedef struct dragon {

int st_row;
int st_col;
int end_row;
int end_col;
int dir;
int gen;

} dragon;

vector<dragon> dragons;

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

// return direction when rotated clockwise to 90 degree
int rot_90(int ori) {

if (ori == 0) return 1;
else if (ori == 1) return 2;
else if (ori == 2) return 3;
else return 0;

}

// return 2^x
int pow_2(int x) {
int sum = 1;
for (int i = 0; i < x; i++) {
sum *= 2;
}

return sum;
}

void paint(vector<dragon> v_dragon) {

int t_r, t_c, e_r, e_c;

for (int i = 0; i < v_dragon.size(); i++) {
t_r = v_dragon[i].st_row;
t_c = v_dragon[i].st_col;
e_r = v_dragon[i].end_row;
e_c = v_dragon[i].end_col;

map[t_r][t_c] = true;
map[e_r][e_c] = true;
}
}

// paint points which is part of the dragon curve;
// dfs
void curve(int cnt, int cnt_obj, vector<dragon> v_dragon) {

// if total generation is reached, return
if (cnt >= cnt_obj) {
paint(v_dragon);
return;
}

// store positions of the dragon curve
int cur_size = v_dragon.size();
int c_row, c_col; // start positions of each line
int n_row, n_col; // end positions of each line
int t_dir;

// initialize
c_row = v_dragon[v_dragon.size()-1].end_row;
c_col = v_dragon[v_dragon.size()-1].end_col;

// draw a curve, searching from backward
for (int i = cur_size-1; i >= 0; i--) {
t_dir = rot_90(v_dragon[i].dir);

n_row = c_row + dR[t_dir];
n_col = c_col + dC[t_dir];

dragon_add = { c_row, c_col, n_row, n_col, t_dir, cnt_obj};

// update
c_row = n_row;
c_col = n_col;
}

curve(cnt+1, cnt_obj, v_dragon);

}

int main() {

cin >> N;
ans = 0;

int t_r, t_c, n_r, n_c, t_d, t_g;
dragon t_dra;
vector<dragon> t_dragons;
//fill(map, map + 101 * 101, false);

for (int i = 0; i < N; i++) {
cin >> t_c >> t_r >> t_d >> t_g;
n_r = t_r + dR[t_d];
n_c = t_c + dC[t_d];
t_dra = {t_r, t_c, n_r, n_c, t_d, t_g};
dragons.push_back(t_dra);
}

for (int i = 0; i < N; i++) {
t_dragons.push_back(dragons[i]);
curve(0, dragons[i].gen, t_dragons);
t_dragons.pop_back();
}

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

cout << ans << endl;

}
``````

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

#### 'Data Structures, Algorithm > SW 역량테스트' 카테고리의 다른 글

 SW 역량테스트 - [백준] 인구 이동 문제 풀이/해답/코드 (C++ / JAVA)  (0) 2020.10.15 2020.10.15 2020.10.15 2020.10.15 2020.10.15 2020.10.15