문제

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

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대
   0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

출력
첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

예제 입력 1
3
3 3 0 1
4 2 1 3
4 2 2 1
예제 출력 1
4

예제 입력 2
4
3 3 0 1
4 2 1 3
4 2 2 1
2 7 3 4
예제 출력 2
11

예제 입력 3
10
5 5 0 0
5 6 0 0
5 7 0 0
5 8 0 0
5 9 0 0
6 5 0 0
6 6 0 0
6 7 0 0
6 8 0 0
6 9 0 0
예제 출력 3
8

예제 입력 4
4
50 50 0 10
50 50 1 10
50 50 2 10
50 50 3 10
예제 출력 4
1992

접근

격자가 100*100 크기밖에 안 되기 때문에 일단 드래곤 커브를 잘 그리기만 하면 격자를 순회하면서 네 꼭짓점에 모두 마킹이 되어 있는지 직접 확인할 수 있겠다 생각했다.

그래서 이 드래곤 커브를 어떻게 그리느냐가 문제였는데, 이전 세대 전체를 그대로 회전한다고 생각하면 너무 어려웠고, 이전 세대에서 마지막으로 도달한 점에서부터 맨 처음 시작점까지 거슬러 올라가며 회전했을 때의 알맞은 위치가 어디일지 찾아주는 식으로 했다.

항상 시계 방향으로 회전하기 때문에, 이전 세대의 선분을 반대 방향으로(다음 세대를 정방향으로 그리려면 반대 방향으로 따라가야 한다!) 거슬러 따라갔을 때

1. 이전 세대에서 위에서 아래로 갔으면 다음 세대에서는 오른쪽에서 왼쪽으로.
2. 이전 세대에서 왼쪽에서 오른쪽으로 갔으면 다음 세대에서는 위에서 아래로.
3. 이전 세대에서 아래에서 위로 갔으면 다음 세대에서는 왼쪽에서 오른쪽으로.
4. 이전 세대에서 오른쪽에서 왼쪽으로 갔으면 다음 세대에서는 아래에서 위로.

그려져야 한다는 규칙이 있었다. 이걸 따라서 다음 점이 어디에 찍힐지를 찾아서 마킹을 했다. 드래곤 커브가 겹쳐져 있어서 여러 번 마킹되더라도 아무 문제가 없다.

그리고 이 문제에서 또 소소하게 헷갈릴 수 있던 지점은 보통 x를 행, y를 열로 많이 생각하는데 이 문제에서는 x축이 열 방향, y 축이 행 방향이었다는 점이다. 그래도 입력에서 방향에 대해 친절하게 화살표까지 주며 알려줘서 실수하지 않고 풀었다.

구현

import java.io.*;
import java.util.*;

class Main {
    static boolean[][] isMarked = new boolean[101][101];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
            markDragonCurve(x, y, d, g);
        }

        int count = 0;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (isMarked[i][j] && isMarked[i + 1][j] && isMarked[i][j + 1] && isMarked[i + 1][j + 1]) {
                    count++;
                }
            }
        }
        
        System.out.println(count);
    }

    private static void markDragonCurve(int x, int y, int d, int g) {
        List<int[]> dragonCurves = new ArrayList<>();
        isMarked[y][x] = true;
        dragonCurves.add(new int[] {y, x});
        if (d == 0) {
            isMarked[y][x + 1] = true;
            dragonCurves.add(new int[] {y, x + 1});
        } else if (d == 1) {
            isMarked[y - 1][x] = true;
            dragonCurves.add(new int[] {y - 1, x});
        } else if (d == 2) {
            isMarked[y][x - 1] = true;
            dragonCurves.add(new int[] {y, x - 1});
        } else {
            isMarked[y + 1][x] = true;
            dragonCurves.add(new int[] {y + 1, x});
        }

        for (int i = 1; i <= g; i++) {
            increaseGeneration(dragonCurves);
        }
    }
    
    private static void increaseGeneration(List<int[]> path) {
        int size = path.size();
        for (int i = size - 2; i >= 0; i--) {
            int[] prev = path.get(i + 1);
            int[] curr = path.get(i);
            int[] last = path.get(path.size() - 1);
            if (prev[0] == curr[0]) {
                // 왼 -> 오
                if (prev[1] + 1 == curr[1]) {
                    isMarked[last[0] + 1][last[1]] = true;
                    path.add(new int[] {last[0] + 1, last[1]});
                } else { // 오 -> 왼
                    isMarked[last[0] - 1][last[1]] = true;
                    path.add(new int[] {last[0] - 1, last[1]});
                }
            } else {
                // 위 -> 아래
                if (prev[0] + 1 == curr[0]) {
                    isMarked[last[0]][last[1] - 1] = true;
                    path.add(new int[] {last[0], last[1] - 1});
                } else { // 아래 -> 위
                    isMarked[last[0]][last[1] + 1] = true;
                    path.add(new int[] {last[0], last[1] + 1});
                }
            }
        }
    }
}