백준 15685번 드래곤 커브

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 Dragon_Curve {
    static int[] dr = {0,-1,0,1};
    static int[] dc = {1,0,-1,0};
    static boolean[][]map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int count =0;

        map = new boolean[101][101];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int col = Integer.parseInt(st.nextToken());
            int row = Integer.parseInt(st.nextToken());
            int dir = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            map[row][col] = true;
            curveDir(col,row,dir,g);
        }
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if(map[i][j]&&map[i][j+1]&&map[i+1][j+1] &&map[i+1][j])
                    count++;
            }
        }
        System.out.println(count);
    }
    public static void curveDir(int col, int row, int dir, int g){
        List<Integer> list = new ArrayList<>();
        list.add(dir);
        for (int i = 1; i < g+1; i++) {
            for (int j = list.size()-1; j >=0 ; j--) {
                list.add((list.get(j)+1)%4);
            }
        }
        for(int i: list){
            col +=dc[i];
            row +=dr[i];
            map[row][col]=true;
        }
    }
}

풀이방법

📢 이 풀이의 핵심은 3세대 드래곤 커브의 동작에서 규칙을 찾아내는게 핵심이다.
전 세대의 커브를 시계방향 회전시켜서 이어 붙이면 다음 세대 드래곤 커브가 된다.

※이때 커브자체는 시계방향 회전이지만, 각각의 선분 방향의 회전만 놓고 본다면 반시계방향으로 돌고 있다.

• 다음 그림을 한번 살펴보자
  
  a선분은 방향 0번으로 오른쪽으로 가고 있고, 이에 대칭되는 a'선분은 a선분의 방향에서 반시계방향 회전한 1번 방향으로 가고 있다.
  🔉이규칙을 찾아내는것이 이문제에서 가장 중요하고 나머지는 이대로 구현만하면 된다.

1. 방향정보만 우선 리스트에 넣는데 예를 들어 처음 방향이 0 이라면 리스트에 0을 넣고 다음 세대로 넘어간다.(0세대)
2. 반시계방향은 0,1,2,3순이므로, 리스트에는 1이 추가되고 다음 세대로 넘어간다.(1세대)
3. 리스트에 현재 0,1이 들어 있고, 다음세대에는 리스트에 방향을 전부 반시계방향 회전시킨 값을 다시 넣어준다. 즉, 1과 2를 넣어준다. 이때 넣는 순서가 핵심이다.
   넣어줄때 리스트의 마지막 값부터 넣어줘야한다. 즉 리스트에는 0,1,2,1이 담긴다.(2세대)
4. 다음세대까지 확인해보면, 리스트에 현재 0,1,2,1이 있으므로 각각 전부 회전시키면 1,2,3,2의 값이 되고 이 값들을 리스트에 추가시켜준다. 이때도 마지막부터 넣어준다.(3세대)
5. 리스트에는 0,1,2,1,2,3,2,1 순서로 담기게 되는것이다.
6. 마지막으로 리스트에 값 순서대로 좌표를 구해서 map에 true표시로 체크한다.
7. map에서 true표시 사각형이 존재하는지 탐색해서 카운팅 해준다.

후기

나는 규칙을 못찾았다. 진짜 진짜진짜 폼 좋은날이었으면 보였을거 같기도 한데 너무 아쉽다. 이런건 어떻게 생각하고 만드는걸까. 뭔가 수학 경시대회 하는거 같다.