[알고리즘] Java / 백준 / 드래곤 커브 / 15685

[알고리즘] Java / 백준 / 드래곤 커브 / 15685

문제

문제 링크

접근 방식

방향을 0 , 1 , 2 , 3 으로 정의한다

1. 0 : 오른쪽 , 1 : 위 , 2 : 왼쪽 , 3 : 아래쪽 인 deltas 배열을 만든다

2. 방향 리스트를 만들고 그 안에 0을 넣는다

3. 드래곤 커브의 세대만큼 반복하면서 기존 방향 리스트에 , 90도 돌린( ( 기존 방향 + 1) % 4) 방향 리스트를 거꾸로 하여 추가로 더한다

   ex ) 0세대 = 0 , 1세대 = 0세대 + ((0세대 각 값 + 1 )% 4 을 거꾸로 정렬)

4. 시작 점과 시작 방향을 입력받고 드래곤 커브 함수로 방향리스트를 얻은 후 시작 점부터 방향리스트의 각 값에 시작 방향을 더한 방향으로 탐색하며 방문한 점들을 true로 처리한다

5. 정사각형 개수를 카운트한다

코드

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

public class Main_15685 {
    static int[][] deltas = {{0,1},{-1,0},{0,-1},{1,0}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        boolean[][] mat = new boolean[101][101];

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

            int[] direction = new int[]{0};
            direction = dragonCurve(0, direction,g);

            mat[y][x] = true;

            for(int j=0;j<direction.length;j++){
                y += deltas[(direction[j]+d)%4][0];
                x += deltas[(direction[j]+d)%4][1];

                mat[y][x] = true;
            }
        }
        int cnt = 0 ;
        for(int i=0;i<100;i++){
            for(int j=0;j<100;j++){
                if(mat[i][j] && mat[i+1][j] && mat[i][j+1] && mat[i+1][j+1]) cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static int[] dragonCurve(int gen, int[] direction, int target){

        for(int i=1;i<=target;i++){
            int len = direction.length;
            int [] newDirection = new int[len*2];

            for(int j=0;j<len;j++){
                newDirection[j] = direction[j];
            }

            for(int j=len;j<len*2;j++){
                newDirection[j] = (direction[len*2 - j - 1] + 1) % 4;
            }
            direction = newDirection;
        }

        return direction;
    }
}