[백준 15685] 드래곤 커브 - JAVA

문제 링크: https://www.acmicpc.net/problem/15685

접근 방법

문제 자체는 구현 문제치고는 직관적이였지만 90도 회전 로직이 있어 어려운 문제였습니다.
처음에는 정점을 ArrayList에 저장해 한 세대$(g)$마다 회전시키자는 생각이였는데
이러면 초기 좌표 기준으로 변화량이 얼마이며,
다음 드래곤 커브에서 복제되는 정점의 변화량들을 새롭게 ArrayList에 저장해야되서
도저히 답이 나오지 않았습니다.

그래서 직접 예시를 그려보면서 반씩 접어가며
현재 세대는 다음 세대의 몇 번째 정점인지 분석했고
현재 세대는 다음 세대와 역순으로 생성된다는 것을 파악하고
방향 또한 반시계로 생성되는 것을 파악하면서 문제를 단순하게 풀 수 있게 되었습니다.

DragonCurve 메서드

dragonCurve라는 메서드에서는
초기 방향을 넣고 세대마다 2배로 증가시켜나가면서
현재 세대의 역순으로 순회해 방향을 반시계로 증가시켜주면서 curveList에 추가해 주었습니다.

드래곤 커브가 완성되면
curveList를 순회하면서 변화된 방향대로 좌표를 변화해나가면서
드래곤 커브 정점을 grid에 추가해주었습니다.

countDragonCurve 메서드

countDragonCurve 메서드에서는
모든 격자를 탐색하면서 1x1 크기의 정사각형의 모서리가
모두 드래곤 커브의 정점인지 파악하도록 단순하게 구현했습니다.

2중 $for$문을 구현해 4개의 정점이 모두 true인지 판별해
모두 true라면 count를 증가시키도록 로직을 구현했습니다.

추가적인 그리드를 생성해 슬라이딩 윈도우 방식으로 이 로직을 최적화 할 수 있었으나
드라마틱한 속도 향상을 이루지 못하기 때문에 현재의 방식으로 구현했습니다.

코드

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


public class Main {
    static StringTokenizer st;
    static int[] dy = {0, -1, 0, 1};
    static int[] dx = {1, 0, -1, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[][] grid = new boolean[101][101];

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            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());

            dragonCurve(x, y, d, g, grid);
        }

        System.out.println(countDragonCurve(grid));
    }

    private static int countDragonCurve(boolean[][] grid) {
        int count = 0;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (grid[i][j] && grid[i][j+1] && grid[i+1][j] && grid[i+1][j+1]) {
                    count++;
                }
            }
        }
        return count;
    }

    private static void dragonCurve(int x, int y, int d, int g, boolean[][] grid) {
        ArrayList<Integer> curveList = new ArrayList<>();
        curveList.add(d);

        for (int i = 0; i < g; i++) {
            for (int j = curveList.size() - 1; j >= 0; j--) {
                curveList.add((curveList.get(j) + 1) % 4);
            }
        }

        grid[y][x] = true;
        for (int nd : curveList) {
            y += dy[nd];
            x += dx[nd];
            grid[y][x] = true;
        }
    }
}