[백준] 15685. 드래곤 커브

문제 링크

[백준] 15685. 드래곤 커브

풀이 과정

시뮬레이션 문제입니다.

세대에 따라 드래곤 커브가 그려지는 규칙이 정해져 있으므로, 문제에서 주어지는 드래곤 커브의 시작 정보(좌표, 방향, 세대)를 바탕으로 직접 2차원 배열에 그려가며 드래곤 커브들을 표현할 수 있습니다.

드래곤 커브는 세대가 지남에 따라 이전 세대가 시계 방향으로 $90^\circ$회전해 끝 점에 붙습니다. 또한, 세대가 지남에 따라 등비 수열(1, 2, 4, 8, 16)로 선분의 개수가 증가하는 것을 알 수 있습니다.

문제의 첫 번째 입력 예시 중 x : 4, y : 2, d : 1, g : 0 이란 예시를 직접 그려가며 알아보겠습니다.

각 세대에 따른 선분의 개수를 우리는 미리 알 수 있으므로( $2^{g}$ ), 먼저 선분의 끝 지점과 그로부터의 바라보는 방향을 저장할 배열을 만들어 둡니다. 0세대의 끝 점과 방향을 0번 인덱스에 저장합니다.

1세대는 0세대를 이용해 만들 수 있습니다. 0세대를 이루는 모든 선분들의 끝 점을 방향을 통해 반시계 방향으로 $90^\circ$ 회전시켜 저장합니다.

왜 반시계 방향으로 회전시키는지에 대한 이유는 다음과 같습니다. 이전 세대를 시계 방향으로 $90^\circ$ 회전시켜 끝 지점에 붙인다는 문제의 규칙은 결국 각 좌표 입장에서 보면, 진행 방향을 반시계 방향으로 $90^\circ$ 회전시킨 결과와 같기 때문입니다.

2세대는 1세대를 이용해 만들 수 있습니다. 1세대를 이루는 모든 선분들의 끝 점을 방향을 통해 반시계 방향으로 90도 회전시켜 저장합니다. 이때 주의할 점은 다음과 같습니다.

• 2번 인덱스에 해당하는 좌표는 1번 인덱스의 방향에 영향을 받음.
• 3번 인덱스에 해당하는 좌표는 0번 인덱스의 방향에 영향을 받음.

3세대도 마찬가지입니다. 새로 그려지는 4, 5, 6, 7번 인덱스의 좌표는 각각 3, 2, 1, 0번 인덱스의 방향에 영향을 받는다는 점을 유의해야 합니다.

static void draw(int sx, int sy, int sd, int tg) {
    Point[] endPoints = new Point[(int) Math.pow(2, tg)];
    int nx = sx + dx[sd], ny = sy + dy[sd];
    endPoints[0] = new Point(nx, ny, sd);
    int gen = 1;

    while (true) {
        if (gen == tg + 1) break;

        int genStartIdx = (int) Math.pow(2, gen - 1);

        for (int i = genStartIdx; i < genStartIdx + Math.pow(2, gen - 1); i++) {
            Point prev = endPoints[(int) Math.pow(2, gen) - i - 1];
            int nd = (prev.d + 1) % 4;
            nx += dx[nd];
            ny += dy[nd];
            endPoints[i] = new Point(nx, ny, nd);
        }

        gen++;
    }

    map[sx][sy] = true;

    for (Point endPoint : endPoints) {
        map[endPoint.x][endPoint.y] = true;
    }
}

로직은 다음과 같습니다.

1. 배열 endPoints 는 입력으로 받은 타겟 세대 tg 를 이용해 $2^{tg}$ 크기로 초기화합니다.
2. endPoints[0] 은 0세대 선분이 끝나는 지점의 좌표 및 이동 방향을 저장해줍니다
3. 1세대부터 타겟 세대( tg )까지 커브의 모든 선분의 끝 점을 저장합니다.
4. 저장된 모든 점들로 2차원 맵에 표시합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {0, -1, 0, 1}, dy = {1, 0, -1, 0};
    static int N;
    static boolean[][] map;
    static final int SIZE = 101;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new boolean[SIZE][SIZE];

        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());
            int d = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());

            draw(y, x, d, g);
        }

        int answer = 0;

        for (int i = 0; i < SIZE - 1; i++) {
            for (int j = 0; j < SIZE - 1; j++) {
                if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) answer++;
            }
        }

        System.out.println(answer);
    }

    static void draw(int sx, int sy, int sd, int tg) {
        Point[] endPoints = new Point[(int) Math.pow(2, tg)];
        int nx = sx + dx[sd], ny = sy + dy[sd];
        endPoints[0] = new Point(nx, ny, sd);
        int gen = 1;

        while (true) {
            if (gen == tg + 1) break;

            int genStartIdx = (int) Math.pow(2, gen - 1);

            for (int i = genStartIdx; i < genStartIdx + Math.pow(2, gen - 1); i++) {
                Point prev = endPoints[(int) Math.pow(2, gen) - i - 1];
                int nd = (prev.d + 1) % 4;
                nx += dx[nd];
                ny += dy[nd];
                endPoints[i] = new Point(nx, ny, nd);
            }

            gen++;
        }

        map[sx][sy] = true;

        for (Point endPoint : endPoints) {
            map[endPoint.x][endPoint.y] = true;
        }
    }

    static class Point {
        int x, y, d;

        public Point(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}