본문 바로가기
CS/Algorithm

[BOJ][C++] 15685 드래곤커브

by 별토끼. 2020. 1. 29.
반응형
문제

https://www.acmicpc.net/problem/15685

 

15685번: 드래곤 커브

첫째 줄에 드래곤 커브의 개수 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,

www.acmicpc.net

풀이

- 커브 그리기

 1. 0단계를 먼저 그려줍니다. 저는 dx, dy 배열을 주고 dir에 따라서 다음 좌표를 그려줬어요. map을 bool로 두고 그렸습니다.

 2. 입력받은 depth를 종료조건으로, dfs로 단계마다 커브를 그렸습니다.  90도 회전하는 nxtx, nxty 배열을 만들어주고 회전을 시켰어요. 이때, 끝점을 계속 기억해주고 업데이트를 해줘야합니다. 좌표값을 저장하고있는 끝점에서 거슬러 올라가면서 i좌표와 i-1좌표의 차이를 파악한 뒤, 기억해놓은 끝점에 회전값(nxtx, nxty을 적용한 값)을 적용시켜야해요. 

 3. 사각형모양으로 모두 true일 경우 answer++를 해줍니다.

코드
#include <iostream>
#include <vector>
using namespace std;
bool map[101][101];
int note[21][4];
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
int nxtx[] = { 1,0,-1,0 };
int nxty[] = { 0,-1,0,1 };
int answer = 0;
void dfs(int cnt, vector<pair<int, int>> v, int depth) {
	if (cnt == depth) {
		return;
	}
	int vsize = v.size();
	int x = v[vsize - 1].first;
	int y = v[vsize - 1].second;
	for (int i = vsize - 1; i > 0; i--) {
		int vx = v[i - 1].first - v[i].first;
		int vy = v[i - 1].second - v[i].second;
		int nx, ny;
		if (vx == 1 && vy == 0) {
			nx = x + nxtx[1];
			ny = y + nxty[1];
		}
		else if (vx == 0 && vy == -1) {
			nx = x + nxtx[2];
			ny = y + nxty[2];
		}
		else if (vx == -1 && vy == 0) {
			nx = x + nxtx[3];
			ny = y + nxty[3];
		}
		else {
			nx = x + nxtx[0];
			ny = y + nxty[0];
		}
		map[nx][ny] = true;
		v.push_back(make_pair(nx, ny));
		x = nx;
		y = ny;
	}
	dfs(cnt + 1, v, depth);
}
int main() {
	//입력
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> note[i][0] >> note[i][1] >> note[i][2] >> note[i][3];
	}
	//커브 그리기
	for (int i = 0; i < n; i++) {
		//0세대
		int y = note[i][0]; int x = note[i][1];
		int dir = note[i][2]; int depth = note[i][3];
		map[x][y] = true;
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		map[nx][ny] = true;

		vector<pair<int, int>> v;
		v.push_back(make_pair(x, y)); v.push_back(make_pair(nx, ny));
		//다음 세대
		dfs(0, v, depth);
		/*for (int p = 0; p < 12; p++) {
			for (int q = 0; q < 12; q++) {
				cout << map[p][q] << ' ';
			}
			cout << endl;
		}
		cout << "-------------------" << endl;*/
	}

	//정사각형 갯수 구하기
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			//cout << map[i][j] << ' ';
			if (map[i][j] == true &&
				map[i + 1][j] == true &&
				map[i][j + 1] == true &&
				map[i + 1][j + 1] == true) {
				answer++;
			}
		}
		//cout << endl;
	}

	cout << answer;

 

반응형

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

[SWEA][C++] 2112 보호필름  (2) 2020.02.17
[BOJ][C++] 17837 새로운 게임2  (3) 2020.02.13
[BOJ][JAVA] 12100 2048(EASY)  (2) 2019.12.29
[Programmers][JAVA] 기능개발  (1) 2019.10.13
[BOJ][3190] 뱀  (2) 2019.09.04

댓글