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

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

---

 

-풀이-

0. 2차원 maze배열을 선언한 뒤, 0으로 초기화 해준다. 이 배열은 드래곤커브가 존재하는 칸을 1로 갱신해줄것이다.

 

1. 각 드래곤 커브마다 point 벡터를 선언해준다.

 

2. 드래곤 커브의 0세대를 만들어 준 뒤, point벡터에 끝점이 맨 뒤로오게 push_back해준뒤, maze배열을 갱신시켜준다.

 

3. 맨뒤의 점이 끝점이므로, 끝점을 기준으로 뒤에서부터 시계방향으로 90도 돌려준뒤, 해당 지점의 maze를 1로 갱신시켜주고, 벡터에 해당 점의 좌표를 넣어준다.

순서는 상관없이 가장 마지막으로 처음 시작한 점을 돌려서 push_back 해주면된다. 그래야 끝점이 벡터의 맨 마지막으로 올 수 있다.

이런식으로 90도를 돌려야 되는데, 각 점을 어떻게 돌릴까?

 

끝점의 좌표와 시계방향으로 돌리고싶은 좌표의 차이를 dx,dy라고 하자.

위를 기준으로 끝점의좌표(x,y+1) - 돌리고싶은 좌표(x,y) = (0,1) 이된다. dx=0, dy=1

차이를 구한 뒤, 끝점의 x좌표에 dy를 빼주고, y좌표에는 dx를 더해주면, 90도 돌아간 좌표를 얻을 수 있다.

예를 들어 (2,2)를 기준으로한뒤, 시계방향으로 돌린다고 해보자. 

(3,2)의 점을 돌린다고 가정하면 (dx,dy) = (2-3 , 2-2) = (-1,0) 이 된다. 이를 (2-dy,2+dx) 해주면, (2,1)이된다.

위와같이 (3,1)을 돌려보면 (dx,dy) = (2-3 , 2-1) = (-1 , 1)이된다. 이를 (2 - 1 , 2 -1) 해주면 (1,1) 이 된다.

위의 그림과 같이 잘 돌아갔다.

 

 

4. 모든 점을 돌렸으면 G세대까지 3번을 반복해준다.

 

5. N번의 드래곤 커브를 완성했으면, (0,0)부터 돌면서 (x,y)==1&&(x+1,y)==1&&(x,y+1)==1&&(x+1,y+1)==1 을 체크해주어, true이면 cnt를 1 증가시켜준다.

 

6.cnt를 출력시켜준다.

 

-시간복잡도-

i세대의 드래곤 커브의 모든 점을 90도 돌리는 것은 2의 i승이 걸린다. 이것을 g세대까지 하는데 걸리는 시간은 시그마를 이용하여 계산해보면 (2^g)-1 이므로, O(2^g)가 된다.

 

이 로직을 n번 반복하므로 O(n*2^g)가 된다.

 

-코드-

 

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

int maze[101][101] = { 0 };
int mv[4][2] = { {0,1},{-1,0},{0,-1},{1,0} };

bool isIn(int x, int y) {
	return x >= 0 && x <= 100 && y >= 0 && y <= 100;
}

int main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		vector<pair<int, int>> point;
		point.push_back({ y,x });
		maze[y][x] = 1;
		if (isIn(y + mv[d][0], x + mv[d][1])) {
			point.push_back({ y + mv[d][0],x + mv[d][1] });
			maze[y + mv[d][0]][x + mv[d][1]] = 1;
		}
		for (int j = 1; j <= g; j++) {
			int psize = point.size();
			pair<int, int> endPoint = point[psize - 1];
			
			for (int k = psize - 2; k >= 0; k--) {
				int dx = endPoint.first - point[k].first;
				int dy = endPoint.second - point[k].second;
				if (!isIn(endPoint.first-dy, endPoint.second+dx)) continue;

				maze[endPoint.first - dy][endPoint.second+ dx] = 1;
				point.push_back({ endPoint.first - dy,endPoint.second + dx });
			}
		}

	}
	int cnt = 0;
	for (int i = 0; i <100; i++) {
		for (int j = 0; j <100; j++) {
			if (maze[i][j] == 1 && maze[i + 1][j] == 1 && maze[i][j + 1] == 1 && maze[i + 1][j + 1] == 1) cnt++;
		}
	}
	cout << cnt << "\n";
}