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

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

풀면서 화딱지가 나서 때려칠까 몇번이나 고민했었던 문제였네요.

 

바로 본론으로 들어가서,

 

포인트는 한 점을 중심으로 어떤 점을 90도 이동시키는 함수를 만드는 일입니다.

드래곤 커브 특성상, 새로운 세대를 만들때 끝점을 중심으로 그 이전 점들을 하나씩 90도 이동시킵니다.

리스트로 구현하려면 리스트의 마지막이 끝점이 됩니다. 끝점의 참조를 저장해두고 역순으로 리스트를 순회하며 90도 회전시킨 점들을 뒤에 추가시킵니다.

이 작업이 끝나면 다시 리스트 맨 마지막에 있는 점이 끝점이 되고, 세대마다 이를 반복하면 되죠.

 

그런데 점을 90도 돌리는 함수 구현 자체가 좀 귀찮습니다.

엄청 어렵다기보단, 명확하게 기준을 세우지 않으면 부호가 헤깔려서 실수하기 십상.

 

저는 기준점에 대해 점의 위치를 1,2,3,4분면으로 분류하고, 각 사분면에 대해 점들을 회전시켰습니다.

구현하실 때 축의 방향, 사분면을 어떻게 정할지 명확하게 정의하고 구현하시길~

 

드래곤 커브를 제대로 만들 수 있다면 나머지는 쉽습니다. 배열에 포인트를 기록하고, 정사각형을 세면 됩니다.

 

 

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

public class Main {
    static boolean[][] map = new boolean[101][101];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
        int 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());
            RotatablePoint seed = new RotatablePoint(x,y);
            int direction = Integer.parseInt(st.nextToken());
            int targetGeneration = Integer.parseInt(st.nextToken());

            List<RotatablePoint> curve = new ArrayList<>();
            curve.add(seed);
            makeCurve(direction, targetGeneration, curve);

            curve.stream().forEach(p -> map[p.y][p.x] = true);
        }

        System.out.println(countSquare());

    }

    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    private static void makeCurve(int direction, int targetGeneration, List<RotatablePoint> curve) {
        RotatablePoint seed = curve.get(0);
        curve.add(new RotatablePoint(seed.x + dx[direction], seed.y + dy[direction]));
        int generation = 0;

        RotatablePoint endPoint = curve.get(curve.size()-1);
        while(generation != targetGeneration) {
            int curveSize = curve.size();
            for (int i = curveSize-2; i >= 0; i--) {
                curve.add(curve.get(i).rotate(endPoint));
            }
            generation++;
            endPoint = curve.get(curve.size()-1);
        }
    }

    private static int countSquare() {
        int count = 0;
        for (int i = 0; i < map.length-1; i++) {
            for (int j = 0; j < map[i].length-1; j++) {
                if(map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1]) count++;
            }
        }
        return count;
    }
}

class RotatablePoint {
    int x;
    int y;

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

    public RotatablePoint rotate(RotatablePoint base) {
        if(base.x == x && base.y == y) return this;

        int sectionNum = getSection(base);
        int diffX = Math.abs(base.x - x);
        int diffY = Math.abs(base.y - y);

        if(sectionNum == 1) return new RotatablePoint(base.x - diffY, base.y + diffX);
        if(sectionNum == 2) return new RotatablePoint(base.x - diffY, base.y - diffX);
        if(sectionNum == 3) return new RotatablePoint(base.x + diffY, base.y - diffX);
        if(sectionNum == 4) return new RotatablePoint(base.x + diffY, base.y + diffX);
        throw new RuntimeException("돌리기 에러");
    }
    /*
    기준 포인트에 대한 상대적 위치
    1사분면, 2사분면, 3사분면, 4사분면
     */
    private int getSection(RotatablePoint base) {
//        System.out.println(String.format("사분면 base : %s, target : %s",base, this));
        //1사분면, +x절편
        if(x > base.x && y >= base.y) return 1;
        //2사분면, +y절편
        if(x <= base.x && y > base.y) return 2;
        //3사분면, -x절편
        if(x < base.x && y <= base.y) return 3;
        //4사분면, -y절편
        if(x >= base.x && y < base.y) return 4;
        throw new RuntimeException("사분면 에러");
    }

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}