[백준] 15685번: 드래곤 커브 - java

문제

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

15685번: 드래곤 커브

 

접근법

문제를 이해하는 데 시간이 많이 걸렸다.

이 직선을 시계 방향으로 90도 회전하면 ↓ 이고, 이걸 끝 점에 붙이면 아래와 같은 드래곤 커브가 생긴다고 이해해서 문제가 도통 이해가 되질 않았다.

 

그래서 예제 1번에 있는 3개의 드래곤 커브 중, 3세대까지 진행되는 2번째 예시를 가지고 규칙을 찾아냈다. 문제 하단에 힌트로 그림이 주어져 있어서 다행이였다.

 

(4, 2)에서 ↑(1) 방향으로 시작하는 드래곤 커브의 0세대~3세대는 위와 같다. 규칙을 찾기 위해 하나씩 방향을 표로 나타내면 다음과 같다.

먼저 알 수 있는 점은 0세대를 제외하고, N세대는 (N - 1)을 그대로 복사한 후, x2번 진행하면 된다. N세대를 반으로 갈랐을 때 왼쪽은 (N - 1)와 똑같고, 오른쪽은 왼쪽과 대칭적인 형태를 보이는 것을 찾아야 한다. 

 

3세대인 경우 왼쪽이 1인 경우 오른쪽은 2(파란색), 왼쪽이 2인 경우 오른쪽은 3(빨간색), 왼쪽이 3인 경우 오른쪽은 0(초록색)인 것을 확인할 수 있다. 즉, 정리하면 아래와 같다.

N세대의 드래곤 커브를 진행하는 경우 (N >= 1)
1. (N - 1)세대의 드래곤 커브를 진행한다.
2. (N - 1)세대의 드래곤 커브를 역순으로 진행한다. 이때 방향을 값에 따라 바꾸어 주어야 한다. (0 -> 1, 1 -> 2, 2 -> 3, 3 -> 0)

 

코드

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

public class Main {

    static int N;
    static boolean[][] grid = new boolean[101][101];

    static int[] dirX = {1, 0, -1, 0};
    static int[] dirY = {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        System.out.println(count());
    }

    private static void dragon(int x, int y, int d, int g) {
        // 0 세대
        grid[y][x] = true;
        x += dirX[d];
        y += dirY[d];
        grid[y][x] = true;

        Point end = new Point(x, y); // 전 세대의 끝 점
        List<Integer> path = new ArrayList<>();
        path.add(d);

        for (int i = 1; i <= g; i++) {
            Point now = new Point(end.x, end.y);
            int size = path.size();

            for (int j = size - 1; j >= 0; j--) {
                int direction = path.get(j);
                switch (direction) {
                    case 0:
                        direction = 1;
                        break;
                    case 1:
                        direction = 2;
                        break;
                    case 2:
                        direction = 3;
                        break;
                    case 3:
                        direction = 0;
                        break;
                }
                path.add(direction);

                int nextX = now.x + dirX[direction];
                int nextY = now.y + dirY[direction];
                grid[nextY][nextX] = true;
                now = new Point(nextX, nextY);
            }

            end = new Point(now.x, now.y);
        }
    }

    private static int count() {
        int cnt = 0;

        for (int r = 0; r < 100; r++) {
            for (int c = 0; c < 100; c++) {
                if (grid[r][c] && grid[r + 1][c] && grid[r][c + 1] && grid[r + 1][c + 1]) {
                    cnt++;
                }
            }
        }

        return cnt;
    }

    static class Point {
        int x, y;

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

 

주의할 점

문제를 확실하게 이해하고 풀자! 힌트가 주어진다면 힌트까지 완벽하게 이해하고 코드를 작성~