드래곤커브

📍 문제 설명

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

15685번: 드래곤 커브

 

💡 접근

첫 좌표가 주어지니 좌표를 하나하나 기억하지 않고 상하좌우 방향의 값을 기억해둬서 풀 수 있다.

0세대 : 0

1세대 : 0 - 1

2세대 : 0 - 1 - 2 - 1

3세대 : 0 - 1 - 2 - 1 - 2 - 3 - 2 - 1

규칙을 보면 2배씩 증가하며 -1세대의 끝점과 현제 새대의 시작점이 반시계 방향으로 대칭이 된다.

 

각 드래곤 커브 마다 그 세대에 맞는 방향 리스트를 구하고 드래곤 커브를 그려서 찾으면 된다.

👩‍💻 코드

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

public class Main {
    static int n, m, v, e, k, r, x, y, answer, cnt;
    static int[] arr, dice;
    static long[] dp;
    static int[][] board, result;
    static boolean[][] visited;
    //x가 열임 - 동북서남
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    static ArrayList<Integer> list;
    static StringBuilder sb;
    static Queue<Integer> q;
    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        result = new int[101][101];
        for(int i = 0; i < n; i++) {
            list = new ArrayList<>();
            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()); // 세대

            list.add(d);
            for(int j = 1; j <= g; j++) {
                //1세대 일땐 한번
                //2세대 일땐 세번
                //3세대 일땐 일곱번
                for(int k = list.size() - 1; k >= 0; k--) {
                    //4일 땐 0으로
                    list.add((list.get(k) + 1) % 4);
                }
            }

            //시작 좌표 체크
            result[y][x] = 1;

            //방향에 따라서 드래곤 커브 그리기
            for(int l : list) {
                x += dx[l];
                y += dy[l];
                result[y][x] = 1;
            }
        }
        System.out.println(T.solution());

    }

    private int solution() {
        //네 꼭지점이 모두 드래곤 커브의 일부인 정사각형 찾기
        int ret = 0;
        for(int i = 0; i < 100; i++) {
            for(int j = 0; j < 100; j++) {
                if(result[i][j] == 1 && result[i][j+1] == 1 && result[i+1][j] == 1 && result[i+1][j+1] == 1) {
                    ret++;
                }
            }
        }
        return ret;
    }

    private static class Point implements Comparable<Point> {
        private int x;
        private int y;
        private int crush;

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

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

        @Override
        public int compareTo(Point o) {
            return this.crush - o.crush;
        }
    }
}