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

---

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

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/15685

해답 코드 : 

 

#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
	dragon dragon_add;
	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};
		v_dragon.push_back(dragon_add);

		// 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 역량테스트 준비 - 백준 알고리즘 문제