[BOJ] 15683 : 드래곤 커브 - travelbeeee

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

---

[ 알고리즘풀이 ]

 1. 드래곤 커브는 X 세대에서는 전 세대까지 왔던 길을 반대로 90도 시계 방향으로 회전 시켜서 진행한다.

예를 들어, 문제 예시 드래곤 커브를 보자.

0세대에서는 x축이 커지는 방향( 0 방향 )으로 이동을 한다.

1세대에서는 그 전 세대까지 왔던 길( 0 방향으로 이동 ) 을 시계 방향으로 회전해서 y 좌표가 감소하는 방향( 1 방향 )으로 이동한다.

2세대에서는 그 전 세대까지 왔던 길( 0 방향 -> 1 방향 ) 을 반대로 1방향 -> 0 방향 순으로 시계 방향으로 회전해서 ( 2방향 -> 1방향 ) 으로 이동한다.

3세대에서는 그 전 세대까지 왔던 길( 0방향 -> 1방향 -> 2방향 -> 1방향 ) 을 반대로 시계 방향으로 회전해서 ( 2방향 -> 3방향 -> 2방향 -> 1방향 ) 으로 이동한다.

 

 즉, 기존까지 이동해온 길들을 저장하고 있다가, 새로운 세대에서는 그 길들을 역순으로 순회하며 방향을 1씩 증가시켜 이동해야한다. 이때, 이동한 부분은 1로 체크한다.

 

 2. 이동이 끝나면, 4개의 점이 1인 갯수를 count 한다.

#include<iostream>
#include<vector>
#include<deque>
#include<algorithm>
int map[101][101] = {}, N, x, y, d, g;

using namespace std;

int countSquare(void) {
	int ans = 0;
	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])
				ans++;
	return ans;
}

void DragonCurve(int x, int y, int d, int g) {
	vector<int> dir;
	dir.push_back(d);

	int sx = x, sy = y;
	map[sy][sx] = 1;
    //첫 번째 세대 이동.
	if (d == 0)
		sx++;
	else if (d == 1)
		sy--;
	else if (d == 2)
		sx--;
	else
		sy++;
	map[sy][sx] = 1;

	for (int i = 1; i <= g; i++) {
		vector<int> temp;
        // 이전세대에서 이동한 길을 역순 + 시계방향회전해서 저장
		for (int j = 0; j < dir.size(); j++)
			temp.push_back((dir[dir.size() - 1 - j] + 1) % 4);
        // 이동.
		for (int j = 0; j < temp.size(); j++) {
			if (temp[j] == 0)
				sx++;
			else if (temp[j] == 1)
				sy--;
			else if (temp[j] == 2)
				sx--;
			else
				sy++;
			map[sy][sx] = 1;
		}
        // 새롭게 이동한 길을 저장.
        for (int j = 0; j < temp.size(); j++)
			dir.push_back(temp[j]);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y >> d >> g;
		DragonCurve(x, y, d, g);
	}
	cout << countSquare();

}

드래곤 커브 예시를 잘 보면 2차원 배열 Map[row][column] 에서

row가 y 값, colum이 x 값인 것을 확인할수 있다.

이 부분을 캐치하지못하고 x 값을 row, y 값을 column으로 생각해서 구현하면

저처럼 '틀렸습니다.' 를 받을 수 있습니다,,,

---