[BOJ 15685] 드래곤 커브 - JAVA, Gold3

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

15685번: 드래곤 커브

 

 

📌구현할 기능 목록📌

1. 드래곤 커브의 개수 그리고 각 커브의 좌표, 방향, 횟수를 입력받는다.

 

2. 101 x 101 크기의 맵을 생성하여, 특정 좌표가 드래곤 커브로 생긴 선분 위의 좌표인지 확인할 수 있도록 

    이중 ArrayList 를 생성한다.

 

3. 각 드래곤 커브에서, 주어진 방향에 맞도록 선분을 추가한다.

 

4. 주어진 횟수만큼 드래곤 커브를 진행하는 함수를 작성한다.

 

5. 생성한 드래곤 커브를 101 x 101 이중 ArrayList에 추가시킨다.

 

6. 3~5번 과정을 드래곤 커브 개수만큼 반복한다.

 

7. 2번에서 생성한 이중 ArrayLIst의 한 격자(1 x 1 정사각형)의 네 꼭지점이 모두 1인 개수를 출력하는 함수를 작성한다.

 

🛠주요 로직🛠

드래곤 커브는 기존 선분 집합들을 끝점을 기준으로 시계방향으로 90도 회전시켜야하는 작업이다.

만약 위 그래프처럼 끝점을 원점(0,0)이라고 가정할 때, A를 반시계방향으로 90도 회전시키면

A(3,4) -> A`(-4,3) 으로 좌표가 바뀌는 것을 확인할 수 있다.

 

 

즉, x와 y 좌표가 뒤바뀌며, x 좌표가 반전된다.

 

만약 시계방향으로 90도 회전시킨다면 x,y 좌표가 뒤바뀌고, y 좌표가 반전될 것이다.

 

단, 우리의 목표는 원점이 아닌 끝점을 기준으로 선분들을 회전시키는 것이다.

 

따라서 끝점과 각 좌표들의 오차를 구하고, 오차를 사용해 위 공식에 대입한 다음 끝점을 좌표에 더해줘야한다.

 

 

예로 A(x1,y1), B(x2,y2) 좌표가 있고, A가 끝점일 때 B가 90도 시계방향으로 회전한다면

 

B(x,y) = (x1 + y1 - y2, y1 + (x1 - x2)*(-1)) 이 된다.

 

💻코드 적용💻

1. 드래곤 커브의 개수 그리고 각 커브의 좌표, 방향, 횟수를 입력받는다.

int N = Integer.parseInt(br.readLine());
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());

    ...
}

...

 

2. 101 x 101 크기의 맵을 생성하여, 특정 좌표가 드래곤 커브로 생긴 선분 위의 좌표인지 확인할 수 있도록 

    이중 ArrayList 를 생성한다.

public static ArrayList<ArrayList<Integer>> map = new ArrayList<>();

for(int i=0;i<=100;++i){
    map.add(new ArrayList<>());
    for(int j=0;j<=100;++j){
        map.get(i).add(0);
    }
}

 

3. 각 드래곤 커브에서, 주어진 방향에 맞도록 선분을 추가한다.

list = new ArrayList<>();

endX = x;
endY = y;

if(d==0){ // 오른쪽
    endX=x+1;
}
else if(d==1){ // 위
    endY=y-1;
}
else if(d==2){ // 왼쪽
    endX=x-1;
}
else if(d==3){ // 아래
    endY=y+1;
}
list.add(new Position(x,y));
list.add(new Position(endX,endY));

 

4. 주어진 횟수만큼 드래곤 커브를 진행하는 함수를 작성한다.

public static void rotate(){
    ArrayList<Position> tempList = new ArrayList<>(list);
    for(Position position:tempList){
        int dx = endX - position.x;
        int dy = endY - position.y;
        list.add(new Position(endX+dy,endY+dx*(-1)));
    }
    int tempEndX = endX;
    int tempEndY = endY;

    endX = tempEndX + tempEndY - tempList.get(0).y;
    endY = tempEndY + (tempEndX - tempList.get(0).x)*-1;
}

 

tempEndX, tempEnxY를 별도로 선언한 이유는 endX, endY를 재정의할 때, endX의 값이 도중에 변경되어 endY의 값 변경에 영향을 미치기 때문이다.

 

끝점 좌표를 나타내는 endX, endY는 드래곤 커브의 시작점을 기준으로 시계방향 90도 회전시킨 좌표가 끝점이 된다.

 

5. 생성한 드래곤 커브를 101 x 101 이중 ArrayList에 추가시킨다.

public static void drawRealMap(){
    for(Position position:list){
        map.get(position.y).set(position.x, 1);
    }
}

 

6. 3~5번 과정을 드래곤 커브 개수만큼 반복한다.

 

7. 2번에서 생성한 이중 ArrayLIst의 한 격자(1 x 1 정사각형)의 네 꼭지점이 모두 1인 개수를 출력하는 함수를 작성한다.

public static int getResult(){
    int answer = 0;
    for(int i=0;i<100;++i){
        for(int j=0;j<100;++j){
            if(map.get(i).get(j)==1 && map.get(i).get(j+1)==1
            && map.get(i+1).get(j)==1 && map.get(i+1).get(j+1)==1){
                answer++;
            }
        }
    }
    return answer;
}

 

⌨제출코드⌨

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

public class Main {

    public static ArrayList<ArrayList<Integer>> map = new ArrayList<>();

    public static class Position{
        int x;
        int y;

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

    public static ArrayList<Position> list;
    public static int endX=0, endY=0;
    public static void rotate(){
        ArrayList<Position> tempList = new ArrayList<>(list);
        for(Position position:tempList){
            int dx = endX - position.x;
            int dy = endY - position.y;
            list.add(new Position(endX+dy,endY+dx*(-1)));
        }

        int tempEndX = endX;
        int tempEndY = endY;

        endX = tempEndX + tempEndY - tempList.get(0).y;
        endY = tempEndY + (tempEndX - tempList.get(0).x)*-1;
    }

    public static void drawRealMap(){
        for(Position position:list){
            map.get(position.y).set(position.x, 1);
        }
    }

    public static int getResult(){
        int answer = 0;
        for(int i=0;i<100;++i){
            for(int j=0;j<100;++j){
                if(map.get(i).get(j)==1 && map.get(i).get(j+1)==1
                && map.get(i+1).get(j)==1 && map.get(i+1).get(j+1)==1){
                    answer++;
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        for(int i=0;i<=100;++i){
            map.add(new ArrayList<>());
            for(int j=0;j<=100;++j){
                map.get(i).add(0);
            }
        }

        int N = Integer.parseInt(br.readLine());
        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());

            endX = x;
            endY = y;

            if(d==0){ // 오른쪽
                endX=x+1;
            }
            else if(d==1){ // 위
                endY=y-1;
            }
            else if(d==2){ // 왼쪽
                endX=x-1;
            }
            else if(d==3){ // 아래
                endY=y+1;
            }
            list.add(new Position(x,y));
            list.add(new Position(endX,endY));

            for(int j=0;j<g;++j){
                rotate();
            }
            drawRealMap();
        }
        bw.write(getResult()+"\n");
        bw.flush();
        bw.close();
    }
}