드래곤 커브는 재귀적으로 정의되었다
세대 드래곤 커브는 세대의 드래곤 커브를 그린뒤 그 끝에서 다시 세대의 드래곤 커브를 90도 시계방향 회전시켜 그린 형태로 정의되었다.
좌표 평면 위에 주어지는 개의 드래곤 커브를 그린 뒤 이므로 좌표 평면을 순회하면서 꼭짓점 네 점이 모두 그려져 있는 정사각형을 찾으면 된다.
하지만 구현에서 가장 어려웠던 점은 바로 세대의 드래곤 커브를 회전 시키는 것이었다.
처음에는 드래곤 커브를 끝점에서의 상대 좌표들의 리스트로 저장하여서 이 상대 좌표들을 회전 시켜볼까 생각했는데 대칭 시키는 것도 아니고 이게 가능할까라는 생각이 들어서 좌표가 아닌 이동 방향을 리스트로 저장해보았다
상하좌우 방향을 에 대응 시킬 때, 이를 시계 방향 회전시키려면 에 대응하면 된다.
단 거꾸로 이동해야 하므로 끝 점 까지 오는데 이동한 방향을 저장한 리스트를 거꾸로 순회하여야 한다. 여기서 Stack을 유지하면서 드래곤 커브를 재귀적으로 구성할까 생각했었는데, 가 최대 10이므로 그냥 미리 전부 만들어 놓고 처리했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static boolean[][] P = new boolean[101][101];
static final int[] dy = {-1, 1, 0, 0};
static final int[] dx = {0, 0, -1, 1};
static final int[] clockwise = {2, 3, 1, 0}; // 상하좌우 방향을 시계방향으로 회전
static List<List<Integer>> curve = new ArrayList<>();
// (y, x)위치 d방향에서 g세대 드래곤 커브를 그린다
static void f(int y, int x, int d, int g) {
P[y][x] = true;
for (int i = 0; i < (1 << g); i++) {
y += dy[curve.get(d).get(i)];
x += dx[curve.get(d).get(i)];
P[y][x] = true;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int d = 0; d < 4; d++) {
List<Integer> temp = new ArrayList<>();
temp.add(d); // 0세대 드래곤 커브 (오른쪽 방향 기준)
for (int g = 1; g <= 10; g++)
for (int i = temp.size() - 1; i >= 0; i--)
temp.add(clockwise[temp.get(i)]);
curve.add(temp);
}
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 문제에서 상하좌우입력을 [0, 4)로 대응시켜주었다.
int d = new int[] { 3, 0, 2, 1 }[Integer.parseInt(st.nextToken())];
int g = Integer.parseInt(st.nextToken());
f(y, x, d, g);
}
int cnt = 0;
for (int i = 0; i < 100; i++)
for (int j = 0; j < 100; j++)
if (P[i][j] && P[i + 1][j] && P[i][j + 1] && P[i + 1][j + 1]) cnt++;
System.out.println(cnt);
}
}