코테_Baekjoon_15685_드래곤커브

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

15685번: 드래곤 커브

 

접근 방법

해당 문제는 규칙을 찾으면 쉽게 풀 수 있는 문제였다. 물론 규칙을 찾는게 쉽진 않지만... 그래도 힌트는 있다. 그래프를 봤을 때 드래곤 커브의 끝점을 기준(N)으로 (N+1)번째와 (N-1)번째는 연관이 있다는 것은 쉽게 알아차릴 수 있다.

드래곤 커브는 끝점을 기준으로 90도를 회전시키므로 N+1번째 점의 방향은 N-1번째의 방향에서 90도를 회전시킨 방향이다.

 

방향을 보면 1 -> 2, 2 -> 3, 3 -> 0, 0 -> 1로 변환한다.

이를 코드로 작성하면 다음과 같다.

 

코드

public class Main {
	static boolean[][] map = new boolean[101][101];
	// 방향 {>,^,<,v}
	static int[][] dirType = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = 0;
		int N = Integer.parseInt(br.readLine());
		for (int n = 0; n < N; n++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int D = Integer.parseInt(st.nextToken());
			int G = Integer.parseInt(st.nextToken());
			
			dragonCurve(x,y,D,G);
		}
		
		for(int y = 0; y < 100; y++) {
			for(int x = 0; x < 100; x++) {
				if(map[y][x] && map[y][x+1]&& map[y+1][x]&&map[y+1][x+1]) answer++;
			}
		}
		
		System.out.println(answer);
	}

	public static void dragonCurve(int x, int y, int D, int G) {
		List<Integer> curves = new ArrayList<>();
		curves.add(D);

		for (int g = 1; g <= G; g++) {
			for (int curve = curves.size() - 1; curve >= 0; curve--)
				curves.add((curves.get(curve) + 1) % 4);
		}

		map[y][x] = true;
		for (int curve : curves) {
			x += dirType[curve][0];
			y += dirType[curve][1];
			map[y][x] = true;
		}
	}
}