[백준 - 15685][Gold 3] - 드래곤 커브 (JAVA)

문제 링크

---

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

 

문제

---

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 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좌표가 증가하는 방향 (↓)
  
  

출력

---

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

 

구현으로 풀릴까??

---

우선 가장 쉬운 방법인 구현을 생각해보자. 위의 행동을 정리하면 다음과 같다.

 

1. 최초 방향의 드래곤 커브(0세대)를 주어진 방향대로 생성
2. g만큼 드래곤 커브 생성
   1. g-1세대 드래곤 커브를 90도 회전
   2. 90회전된 드래곤 커브의 끝점과 g세대 드래곤 커브 끝점을 연결
3. 모든 드래곤 커브의 끝점으로 둘러쌓여 있는 1X1 크기의 정사각형 탐색

 

이 문제를 풀기 위해선 드래곤 커브가 뭔지 알아야 한다. 드래곤 커브는 기존의 도형을 시계방향으로 90도 돌린 후 시작점과 가장 먼 점(끝점)을 서로 연결한 도형을 말한다. 

 

직접 도형을 돌려서 연결하고자 하니 도형을 돌리는 기준인 원점을 잡는게 굉장히 어려워진다. 매번 도형의 크기가 바뀌기 떄문에 매번 모든 도형의 좌표를 원점을 기준으로 옮기는 일은 어려울 것이다.

 

그래서 도형을 직접 돌리는 것이 아니라 방향을 생각해보자.

 

0세대를 이용해서 1세대를 그림으로 표현하면 다음과 같다.

 

1. 0세대를 90도 회전

0세대 드래곤 커브

 

0세대 드래곤 커브를 시계방향으로 90도 회전함

 

2. 2개의 드래곤 커브를 끝점끼리 연결

끝점끼리 연결한 드래곤 커브

 

3. 이동 방향을 시작점 방향에서 직진 방향으로 변경

완성된 1세대 커브

 

위의 방법을 정리하면 다음과 같은 규칙이 있다는 것을 알 수 있다.

 

1. 기존 n-1세대 드래곤커브를 시계방향으로 90도 회전
2. 기존 n-1 세대와 끝점 연결
3. 돌린 드래곤커브의 모든 방향을 역방향으로 변경

 

위의 방법을 방향만 생각하면 다음과 같은 방법으로 드래곤 커브를 만들 수 있다.

 

1. 기존 n-1세대 드래곤커브 방향을 모두 시계방향으로 90도 회전
2. 돌린 드래곤커브의 모든 방향을 역방향으로 변경
3. 역순으로 기존 드래곤 커브와 연결

 

위의 방법을 이용하면 좌표를 저장하지 않고 방향만 돌린 후 모든 방향이 결정되었을 때 시작점부터 방향대로 움직인다면 드래곤 커브를 만들 수 있다!

 

시간 복잡도를 구해보자

---

 

O(N)
= (모든 시작 좌표의 개수) * (세대) * (모든 드래곤 커브의 방향)
= N * g * (최대 드래곤 커브의 이동 방향 개수)
= N * g * 2^g

 

N은 최대 10, g는 최대 10이므로 최대 연산 횟수는 10 * 10 * 2^10 = 102,400이다. 시간제한 1초의 연산 횟수인 1억부다 작으므로 주어진 시간안에 해결할 수 있다!

 

해결 코드

---

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
		
        //이동 방향
        int[] directionX = {1,0,-1,0};
        int[] directionY = {0,-1,0,1};

        boolean[][] visited = new boolean[101][101];
		
        //모든 시작점을 이용해서 드래곤 커브를 생성
        for(int i=0;i<N;i++){
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            Coordinate startDirectionVector = new Coordinate(directionX[input[2]],directionY[input[2]]);

            List<Coordinate> directionVectors = getDirection(startDirectionVector,input[3]);

			//드래곤 커브 꼭짓점 방문 처리
            Coordinate curr = new Coordinate(input[0],input[1]);
            visited[curr.x][curr.y] = true;

            for(Coordinate directionVector : directionVectors){
                Coordinate next = new Coordinate(curr.x + directionVector.x, curr.y + directionVector.y);

                visited[next.x][next.y] = true;
                curr = next;
            }
        }

        int count = 0;
		
        //4개의 꼭짓점이 모두 드래곤 커브의 요소면 개수 증가
        for(int x=1; x<=100; x++){
            for(int y=1; y<=100; y++){
                if(!visited[x][y]){
                    continue;
                }
                if(!visited[x-1][y]){
                    continue;
                }
                if(!visited[x][y-1]){
                    continue;
                }
                if(!visited[x-1][y-1]){
                    continue;
                }
                count++;
            }
        }

        System.out.println(count);
    }

	//드래곤 커브를 만드는 모든 방향벡터를 구하는 메소드
    public static List<Coordinate> getDirection(Coordinate start,int generation){
        List<Coordinate> directionVectors = new ArrayList<>();
        directionVectors.add(start);

        for(int i=1;i<=generation;i++){
            List<Coordinate> next = new ArrayList<>();
			
            //이전 세대의 방향을 시계방향 90도로 회전
            for(Coordinate vector : directionVectors){
                Coordinate rotateVector = new Coordinate(vector.y,-vector.x);
                rotateVector = new Coordinate(rotateVector.y,-rotateVector.x);
                rotateVector = new Coordinate(rotateVector.y,-rotateVector.x);

                next.add(rotateVector);
            }

			//역방향으로 변경후 역순으로 이전 드래곤커브와 연결
            for(int j=next.size()-1;j>=0;j--){
                Coordinate reverseVector = new Coordinate(-next.get(j).x,-next.get(j).y);
                directionVectors.add(reverseVector);
            }
        }

        return directionVectors;
    }
}
class Coordinate{
    int x;
    int y;

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

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

 

 

실행 결과

---

 

 

제한시간인 1초 안에 문제가 해결되었다!

 

키워드

---

• 90도 회전
  
  • rotate[i][j] = arr[j][N -1 - i]는 반시계 방향으로 만들어 준다.
    •  
  • rotate[j][i] = arr[[N -1 - i][j]는 시계 방향으로 만들어 준다.

 

팁

---

• 시계방향 90도는 반시계방향 90도를 3번하면 된다.