백준 15685 [C++]

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

1. 풀이방법

 

- 처음에 드래곤커브 그림만 보아서는 무슨 규칙인지....그려봐도 무슨규칙인지......반복문으로 표현이 가능한지....

 

- 전혀 풀이방법이 생각이 안나다가.... 문제를 계속 보면 문제에서 직접 방향 0,1,2,3에 대한 정보가 나오고 개인적으로는

 

- 강조하는 느낌....?이 들었습니다.

 

- 드래곤커브를 세대별로 써보면 다음과 같습니다. (방향 0으로 시작할 때)

   - 0세대 :0

   - 1세대 :01

   - 2세대 :0121

   - 3세대 :01212321

   - 4세대 :0121232123032321

 

- 잘보시면 규칙이 있습니다 이전세대에서 다음세대로 넘어갈때 이전세대의 길이만큼 늘어나는데

 

- 이전세대의 역순 INDEX (뒤쪽부터) (curve[reverindex]+1) % 4 가 다음세대에 차례로 추가됩니다.

   (저도 찾지 못해서 힌트를 얻어 알아냈습니다.....)

 

- 이것만 알게되면 방향순서를 차례로 구해서 visit에 방문체크만 해주시면 됩니다.....!

 

 

 

 

2. 주의사항

 

- 좌표계가 제가 평소 익숙하게 (다른 문제에도 자주) 다루는 좌표계랑 반대입니다. 주의 !

 

 

 

 

3. 나의코드

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

int N;
int x, y, d, g;
bool visit[102][102];
int resultcount;
int dy[4] = { 0,-1,0,1 };// 동북서남(0,1,2,3)
int dx[4] = { 1,0,-1,0 };
int dragon[1024];
void setvisit() {
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 101; j++) {
			visit[i][j] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	setvisit();
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y >> d >> g;
		dragon[0] = d;
		visit[y][x] = true;
		//드래곤커브 방향 구하기
		for (int j = 1; j <= g; j++) { //세대별로
			int reverseindex = pow(2, j - 1) - 1;
			for (int k = pow(2, j - 1); k < pow(2, j); k++) {
				dragon[k] = (dragon[reverseindex] + 1) % 4;
				reverseindex--;
			}
		}
		for (int j = 0; j < pow(2, g); j++) {//방문처리
				x += dx[dragon[j]]; y += dy[dragon[j]];
				visit[y][x] = true;
		}
	}
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 101; j++) {
			if (visit[i][j] == true && visit[i + 1][j] == true && visit[i][j + 1] == true && visit[i + 1][j + 1] == true)
				resultcount++;
		}
	}
	cout << resultcount << "\n";
	return 0;
}