[BOJ 15685] 드래곤 커브

문제출처

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

15685번: 드래곤 커브

 

문제풀이

정말 어려웠던 문제였다. 문제풀이의 핵심은 세대가 증가할 때 마다 방향전환의 규칙성을 찾는것이 핵심이다.

0 (동쪽)방향을 기준으로 예시를 들어보면 이해하는데 조금 더 편하다.

 

0세대 : 0

1세대 : 0 1

2세대 : 0 1 | 2 1

3세대 : 0 1 2 1 | 2 3 2 1

4세대 : 0 1 2 1 2 3 2 1 | 2 3 0 3 2 3 2 1

 

예시를 보면 알 수 있듯이 1세대에서 2세대의 방향정보를 만드는 규칙은 마지막 부분 +1을 추가하는 것이다. 2세대에서 3세대를 만들때도 같은 규칙을 사용한다. 하지만 +1을 계속하면 {0,1,2,3}의 인덱스가 깨지므로 +1한 값의 %4를 해주면 해당 세대의 방향정보를 알 수 있다.

 

그다음부터는 정말 단순한 구현이다. 이때 문제에서는 꼭지점을 기준으로 드래곤 커브를 그리고 있다. 이 기준을 단순 2차원 배열로 바꾸어 계산해 주면 된다. 2차원 배열에 표현하기 때문에 (x,y) <= 100인 조건은 (x,y) <= 101로 변환하여 풀이한다.

개인적으로 저 규칙을 알아내는것이 매우 힘들었다. 시간이 지나고 다시 풀어봐야 겠다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_15685/BOJ_15685/boj15685.cpp

sw93/algorithm

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 101;
const int dy[] = { 0, -1, 0, 1 };
const int dx[] = { 1, 0, -1, 0 };
int n, y, x, d, g;
int map[MAX][MAX];
int solve() {
	cin >> n;
	while (n--) {
		cin >> x >> y >> d >> g;
		vector<int> dir;
		dir.push_back(d);
		map[y][x] = 1;
		for (int i = 0; i < g; i++) {
			int dirSize = dir.size();
			for (int j = dirSize - 1; j >= 0; j--) {
				dir.push_back((dir[j] + 1) % 4);
			}
		}
		for (int i = 0; i < dir.size(); i++) {
			y += dy[dir[i]];
			x += dx[dir[i]];
			if (y < 0 || x < 0 || y >= MAX || x >= MAX) continue;
			map[y][x] = 1;
		}
	}
	int ret = 0;
	for (int r = 0; r < MAX - 1; r++) {
		for (int c = 0; c < MAX - 1; c++) {
			if (map[r][c] == 1 && map[r + 1][c] == 1 && map[r][c + 1] == 1 && map[r + 1][c + 1] == 1) {
				ret++;
			}
		}
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout<<solve();
	return 0;
}