[백준][15685번] 드래곤 커브

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

15685번: 드래곤 커브

 

풀이과정

1. 주어진 입력에 드래곤커브에 따라 map에 라인을 그려주었다. (Stack 구조가 이용됨)

 

2. 처음 시작 위치에서 방향만을 벡터에 저장했다. 스택과 같이 뒤에서 부터 저장 된 방향을 이용하면

이전 세대 드래곤커브를 시계방향으로 돌려 마지막에 붙인 효과를 볼 수 있다.

 

 

소스코드

#include<stdio.h>
#include<vector>
using namespace std;
int map[101][101];

struct dragon {
	int x;
	int y;
	int d;
	int g;
}typedef drg;

int N, answer = 0;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
vector<drg> info;

int getClockWiseDir(int n)
{
	switch (n) {
	case 0: return 1;
	case 1: return 2;
	case 2: return 3;
	case 3: return 0;
	}
}

void dragonCurve(int num)
{
	vector<int> dir;
	//0세대
	dir.push_back(info[num].d);
	int x = info[num].x, y = info[num].y;
	map[y][x] = 1;
	x += dx[info[num].d];
	y += dy[info[num].d];
	for (int i = 1; i <= info[num].g; i++) {
		for (int j = dir.size(); j > 0; j--) {
			map[y][x] = 1;
			int nextDir = getClockWiseDir(dir[j-1]);
			dir.push_back(nextDir);
			x += dx[nextDir];
			y += dy[nextDir];
			if (x < 0 || y < 0 || x > 100 || y > 100) return;
		}	
	}
	if (x < 0 || y < 0 || x > 100 || y > 100) return;
	map[y][x] = 1;
}

bool checkDragonCurve(int y, int x) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			int nx = x + j;
			int ny = y + i;
			if (nx < 0 || ny < 0 || nx > 100 || ny > 100) return false;
			if (map[ny][nx] == 0) return false;
		}
	}
	return true;
}

void solution()
{
	for (int i = 0; i < info.size(); i++) {
		dragonCurve(i);
	}

	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (map[i][j] == 0) continue;
			if (checkDragonCurve(i, j)) {
				answer++;
			}
		}
	}
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int x, y, d, g;
		scanf("%d %d %d %d", &x, &y, &d, &g);
		drg tmp = { x,y,d,g };
		info.push_back(tmp);
	}
	solution();
	printf("%d\n", answer);
}

 

결과