[백준 15685] 드래곤 커브 [Java]

문제

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

 

---

풀이

문제에서 주어진 조건대로 드래곤 커브를 만들고, 네 꼭짓점이 드래곤 커브의 일부분인 1x1 크기의 정사각형의 수를 세는 문제다.

우선, 드래곤 커브의 규칙부터 알아보자.

시작점에서 시작방향으로 1칸 이동 후 끝점을 기준으로 지금까지 그린 드래곤 커브를 시계 방향으로 90도 회전해야 한다.

이때, 드래곤 커브의 모든 변은 위치와 방향에 관계없이 결국 시계 방향으로 90도 회전을 한다.

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

방향 변화에 대해 다음과 같은 규칙이 성립한다.

• 0 → 1
• 1 → 2
• 2 → 3
• 3 → 0

각 부분 드래곤 커브들의 방향 변화 규칙을 알았으니 생성 순서를 정해주자.

현재의 끝점에서 이전에 그린 드래곤 커브들을 반대로 그려줘야 한다.

d에서 시작해 각 세대마다 드래곤 커브들은 $2^i$씩 증가하며, $d_i = d_{i - 1} mod 4$가 성립한다.

이를 다음과 같이 구현할 수 있다.

    private static void simulation(int x, int y, int d, int g) {
        A[x][y] = true;
        List<Integer> path = new ArrayList<>(List.of(d));
        for (int i = 0; i < g; ++i) {
            final int G = (int) Math.pow(2, i);
            for (int j = 0; j < G; ++j) {
                path.add((path.get(G - j - 1) + 1) % 4);
            }
        }

문제에서 “좌표 평면의 x축은 → 방향, y축은 ↓ 방향”라고 주어졌는데 편의상 x와 y를 반전했다.

        while (N-- > 0) {
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            final int x = input[0], y = input[1];
            final int d = input[2], g = input[3];

            // Solve
            simulation(y, x, d, g);
        }

이전에 구한 드래곤 커브의 방향에 따라 한 칸씩 방문해주면 된다.

문제에서 격자의 범위를 0 ~ 100으로 지정했기 때문에 이를 벗어난 드래곤 커브는 무시하자.

        for (int dir : path) {
            final int nx = x + dx[dir];
            final int ny = y + dy[dir];
            if (isValid(nx, ny)) {
                if (!A[nx][ny])
                    A[nx][ny] = true;
                x = nx;
                y = ny;
            }

        }
    }

드래곤 커브가 지나는 각 꼭짓점이 한 칸을 의미하므로 드래곤 커브를 만들면서 방문한 2x2크기의 정사각형을 모두 세주면 된다.

        int cnt = 0;
        for (int i = 0; i < 100; ++i) {
            for (int j = 0; j < 100; ++j) {
                if (A[i][j] && A[i + 1][j] && A[i][j + 1] && A[i + 1][j + 1]) {
                    ++cnt;
                }
            }
        }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/15685.java