백준 드래곤 커브(15685)

드래곤 커브(15685)

드래곤 커브는 재귀적으로 정의되었다
$n (n > 0)$세대 드래곤 커브는 $n - 1$세대의 드래곤 커브를 그린뒤 그 끝에서 다시 $n - 1$세대의 드래곤 커브를 90도 시계방향 회전시켜 그린 형태로 정의되었다.

좌표 평면 위에 주어지는 $N$개의 드래곤 커브를 그린 뒤 $x, y <= 100$이므로 좌표 평면을 순회하면서 꼭짓점 네 점이 모두 그려져 있는 정사각형을 찾으면 된다.

하지만 구현에서 가장 어려웠던 점은 바로 $n - 1$세대의 드래곤 커브를 회전 시키는 것이었다.
처음에는 드래곤 커브를 끝점에서의 상대 좌표들의 리스트로 저장하여서 이 상대 좌표들을 회전 시켜볼까 생각했는데 대칭 시키는 것도 아니고 이게 가능할까라는 생각이 들어서 좌표가 아닌 이동 방향을 리스트로 저장해보았다

상하좌우 방향을 $[0, 4)$에 대응 시킬 때, 이를 시계 방향 회전시키려면 $[2, 3, 1, 0]$에 대응하면 된다.

단 거꾸로 이동해야 하므로 끝 점 까지 오는데 이동한 방향을 저장한 리스트를 거꾸로 순회하여야 한다. 여기서 Stack을 유지하면서 드래곤 커브를 재귀적으로 구성할까 생각했었는데, $g$가 최대 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);
	}
	
}