드래곤 커브

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점이 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

===풀이===

우선 예시에 나와있는 드래곤 커브의 곡선 변화를 살펴보자.

0세대 → 

1세대 ↑ 

2세대 ←  ↓ 

3세대  ← ↓ ← ↑

이런식으로 이동했다.

그런데 가만히 보면 그냥 움직인게 아니라 어느정도의 규칙성이 있다. (자세히 봐야 안다...후..)

맨처음 0세대~ 2세대까지 순서는 

→  ↑  ←  ↑ 요 순서대로 이동을 했다.  

3세대를 보면

 ← ↓ ← ↑ 이렇게 움직였다.

2세대까지 움직인 거리와, 3세대까지 움직인 규칙을 살펴보면

→  ↑  ←  ↑     <====2세대 마지막

↑  ←  ↓   ←    <====3세대 시작

뭔가 규칙이 보이는가?? 

그렇다. 움직인 화살표가 4번째 마다 매핑이 되는 걸 알 수가 있다.

다시 풀어서 얘기 하면

→	↑	←	↑
↑	←	↓	←

<~2세대 까지와 3세대가 진행된 방향>  2세대와 3세대 위아래가 매칭이 되었다는 것을 도출 해낼 수 있다.

즉, 아래 표를 보면 

→	↑	←	↓
↑	←	↓	→

<최종매핑 표1>

이런식으로 매핑이 되어진다.

결국 3세대의 모양은 2세대에서 마지막 부터 차례대로 (스택에서 쌓인게 나온다는 느낌으로) 

최종 매핑표에 맞게끔 모양이 그려진다는 것을 확인 할 수 있다.

→	↑	←	↑
			←

→	↑	←	↑
		↓	←

→	↑	←	↑
	←	↓	←

→	↑	←	↑
↑	←	↓	←

그래서 나는 방향전환을 한번 아래와 같이 표현해 보았다

(arrayList를 사용했음)

// 0 1 2 3

//오른쪽, 위 왼족, 아래

static int dx [] = {1,  0, -1, 0,};

static int dy [] = {0, -1, 0, -1,};

//순서대로 오른쪽, 위, 왼쪽, 아래로 탐색을 했음

ArrayList<Integer> al = new ArrayList<>();

al.add(0);

al.add(1);

al.add(2);

al.add(1);

이런식으로 2세대 까지 들어갈 것이다. 

int current_size = al.size();

//항상 거꾸로 부터 탐색을 해줘야 한다.

for(int i=current_size-1; i>=0; i—){

 

    int next_dir = (al.get(i) + 1) % 4; 를 하게 해주면 해당 화살표에 맞게끔 다음 방향으로 전환이 되어지게 만들어 준다.

    //다음 방향을 저장해준다.

    al.add(next_dir);

}

최종 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
 
 
    static int dx [] = {1,  0, -1,0,};
    static int dy [] = {0, -1, 0,1,};
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.valueOf(br.readLine());
        int arr [][] = new int [1000][1000];
        ArrayList<Integer> al = new ArrayList<>();
        boolean check_area [][] = new boolean [1000][1000];
        for(int i=0; i<n; i++) {
            String line [] = br.readLine().split(" ");
            arr = new int [1000][1000];
            al = new ArrayList<>();
            int start_x = Integer.valueOf(line[0]);
            int start_y = Integer.valueOf(line[1]);
            int dir = Integer.valueOf(line[2]);
            check_area[start_x][start_y] = true;
 
            int next_x = start_x + dx[dir];
            int next_y = start_y + dy[dir];
            check_area[next_x][next_y] = true;
            int generations = Integer.valueOf(line[3]);
 
            //첫번째 방향을 넣어준다. 
            al.add(dir);
 
            int next_dir = dir;
            for(int k=0; k<generations; k++) {
                int al_size = al.size();
 
                //해당 리스트의 사이즈만큼 맨 뒤에서부터 반복을 해준다. 
                for(int z = al_size -1; z>=0;z--) {
 
                    //다음 방향은 현재 얻어온 방향에 매칭되는 값을 넣어준다.
                    next_dir = (al.get(z)+1) % 4;
                    next_x = next_x + dx[next_dir];
                    next_y = next_y + dy[next_dir];
                    check_area[next_x][next_y] = true;
                    al.add(next_dir);
                }
 
 
            }
        }
 
        int total_count = 0;
        for(int x =0; x<100; x++) {
            for(int y=0; y<100; y++) {
 
                if(check_area[x][y] && check_area[x+1][y] && check_area[x][y+1] && check_area[x+1][y+1])
                    total_count++;
 
            }
        }
 
        System.out.println(total_count);
 
 
    }
 
}