[BAEKJOON] 15685번 드래곤 커브

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

15685번: 드래곤 커브

문제조건

1. 시작점, 시작방향, 세대가 주어진다.
2. K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.
3. 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

접근방법

 

같은 모양이 계속해서 반복해서 추가되는 것을보고, DP아니면, 재귀의 형식으로 풀 수 있지 않을까? 라고 생각이들었다.

하지만 아무래도 DP의 경우는 정규화된 식이 떠오르지 않았고, 재귀의 경우 Top-down Approach밖에 떠오르지 않았다.

이건 알고리즘적 접근법으로 가면 안될라나라는  생각이 드는 찰나에, 문제의 조건을 한번 살펴봤다.

90º 시계 방향 회전?? 그 다음에 그걸 끝점에 붙인다?

 

문제에서 그림을 보니, 내가 알고 싶은것은 드래곤 커브 모양이 100 x 100 격자에 어디 찍히느냐 이기때문에 k세대 드래곤을 그리고 다음으로 진행하는 방향이 가장 중요했던 것이다.

방향은 k세대 까지 그렸던 방향들의 뒤에서부터 시작해 앞으로 오면서 각각 그에 해당하는   90º 반시계방향으로 진행한다. 

 

쉽게 생각하면 이때까지 그렸던 방향들을 따로 저장해두고, 저장한 크기만큼 저장해준 방향들을 역순으로 탐색하면서 90º 반시계방향으로 추가해주는 작업을 반복해주면 된다.

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };
int n, map[101][101];
int res;
int main(){
	cin >> n;
	for (int cur = 0; cur < n; cur++) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		vector<int> dir;
		dir.push_back(d);
		for (int i = 0; i < g; i++) {
			vector<int> v = dir;
			//반시계 방향(대칭)
			for (int j = v.size() - 1; j >= 0; j--) dir.push_back((v[j] + 1) % 4);				
		}
		map[y][x] = 1;
		for (int i = 0; i < dir.size(); i++) {
			y = y + dy[dir[i]];
			x = x + dx[dir[i]];
			if (y < 0 || y > 100 || x < 0 || x > 100) continue;
			map[y][x] = 1;
		}
	}

	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]) res++;
		}
	}
	cout << res;
}

• Out Of Bounds 를 조심하자!! map의 반경은 0부터 100까지! 
  • 위 코드에서 마지막에 이중 for문을 돌면서 i, j 를 99까지 탐색해줘야 i+1, j+1에서 100을 초과하지 않는다.