[백준] 15685번 : 드래곤 커브 (C++)

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

15685번: 드래곤 커브

삼성 SW 역량 테스트 기출문제이다. 

드래곤 커브의 방향은 다음과 같다.

0 (동쪽)

1 (북쪽)

2 (서쪽)

3 (남쪽)

 

그리고 각 세대의 드래곤 커브는 일정한 방향 규칙을 갖는다.

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

 

N세대 : (N-1)세대 + (N-1)세대의 역순으로 (i+1)%4

 

또 하나 유의해야하는 것은, 100 X 100 크기의 격자이다. 따라서, 처음에 int map[100][100]가 아닌 int map[101][101]로 설정해줘야한다. 그림을 그려보면 왜그런지 이해될 것이다.

 

추가적으로, 마지막 cnt를 계산할때 정사각형 기준으로 맨왼쪽위 좌표를 기준으로 삼아서 따로 범위체크를 해줄 필요가 없었다.

 

아래는 전체코드이다.

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

int N;
int X, Y, D, G;
int map[101][101];
int dx[4] = { 0,-1,0,1 }; //0:동, 1:북, 2:서, 3:남
int dy[4] = { 1,0,-1,0 };
vector<int> dir;
int cnt;

//방향 규칙
// 0세대 : 0 , 1세대 : 0 1, 2세대 : 0 1 2 1 , 3세대 : 0 1 2 1 2 3 2 1
// 규칙 : (N)세대 : (N-1)세대 + (N-1)세대의 (i+1)%4 역순으로 붙이기
void DragonCurve() {
	int size = dir.size();
	for (int i = size-1; i >=0; i--){
		int nextdir = (dir[i] + 1) % 4;
		Y += dx[nextdir];
		X += dy[nextdir];
		map[Y][X] = 1;
		dir.push_back(nextdir);
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++){
		cin >> X >> Y >> D >> G;
		dir.clear();

		//0세대
		map[Y][X] = 1;
		Y += dx[D];
		X += dy[D];
		map[Y][X] = 1;
		dir.push_back(D);
		
		//N세대 그리기
		while (G--) DragonCurve();
	}
	for (int i = 0; i < 100; i++){ //100x100
		for (int j = 0; j < 100; j++) {
			if (map[i][j] && map[i + 1][j] && map[i][j+1] && map[i+1][j+1]) {
				cnt++;
			}
		}
	}

	cout << cnt << endl;
}