[BOJ_15685] 드래곤 커브 (Java)

문제링크

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

15685번: 드래곤 커브

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 시뮬레이션

드래곤커브 문제를 봤을 때 굉장히 난해하다는 생각을 받았었습니다. 어떻게 그래프를 특정 점에서 90도씩 돌릴 수 있을까 고민을 많이 했는데, 생각해보니 그래프를 그릴 때 해당 점에서 어느 방향으로 이동하였는지만 알면 드래곤 커브를 구할 수 있었습니다.

 

드래곤 커브 문제는 특정 시작 점에서 시작 방향으로 1칸 이동하는 0세대 그래프에서 부터 구현됩니다. 0세대 그래프를 구현하였다면 1세대 그래프는 그 0세대 그래프를 시계방향으로 회전하여 구할 수 있습니다. 2세대 그래프는 1세대 그래프의 끝점에서 회전하여 구할 수 있습니다. 따라서 N세대 그래프는 N-1세대 그래프의 끝점에서 90도를 회전해 붙여 만들 수 있게 됩니다.

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

드래곤 커브를 이해하기 위하여 위 예를 알아보겠습니다.

시작점 $(0,0)$에서 시작하여 오른쪽 방향으로 진행을 한다고 하면 첫번째 그래프 모양이 0세대 그래프가 됩니다.

두번째 그래프를 보면 끝점 $(1,0)$에서 시계방향으로 회전을 시켜 붙여 1세대 그래프를 구할 수 있습니다.

$(1,-1)$ 점에서 시계방향으로 돌려 붙이면 2세대 그래프를 알수 있습니다.

$(0,-2)$ 점에서 시계방향으로 2세대 그래프를 돌려 붙이면 3세대 그래프를 알 수 있습니다.

 

이때 회전을 할 때마다 특정 점의 방향을 생각해봅시다. 0세대의 그래프를 구하기 위해 $(0,0)$에서 $(1,0)$으로 오른쪽 방향으로 선을 그어주었습니다. 그 뒤 $(1,0)$에서는 $(0,0)$에서 왔던 방향의 반시계인 위쪽으로 선을 그어주어 1세대 그래프를 만듦니다.

2세대 그래프를 구할 때 보면 $(1,-1)$에서 보면 $(1,0)$에서 1세대 그래프를 구하기 위해 위쪽으로 선을 그어주었는데, 그에 반 시계 방향으로 왼쪽으로 선을 그어주어 해결할 수 있습니다. $(0,0)$의 점이 회전하는 것은 왼쪽으로 이동한 $(0,-1)$로 가서 위쪽으로 선을 그어주면 되는 것입니다.

 

따라서, 특정점에서 그어지는 방향은 과거에 그었던 방향과 연관이 있게 됩니다. 과거에 그었던 방향이 위라면 반시계 방향인 왼쪽으로 왼쪽으로 그어졌다면 아래쪽으로 아래쪽으로 그어졌다면 오른쪽으로 오른쪽이라면 위쪽으로 그어집니다. 그리고 가장 최근 그어진 방향부터 확인하여 그 시계방향으로 그어주고 그 점으로 이동하고 다음을 찾아서 그어주는 식으로 구현하면 드래곤 커브를 구할 수 있습니다.

구현코드

package backjoon_15685;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);


        boolean[][] location = new boolean[101][101];
        int curveSize = sc.nextInt();

        while (curveSize-- != 0) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int d = sc.nextInt();
            int g = sc.nextInt();
            ArrayList<Integer> directions = new ArrayList<>();
            directions.add(d);
            if(g != 0)
                findDirection(g, directions);
            makeCurve(location, x, y, directions);
        }

        int count = countingSquare(location);
        System.out.println(count);
    }

    private static void makeCurve(boolean[][] location, int x, int y, ArrayList<Integer> directions) {
        //첫 점
        location[x][y] = true;
        for (int i = 0; i < directions.size(); i++) {
            int direction = directions.get(i);
            if (direction == 0) {
                x += 1;
            } else if (direction == 1) {
                y -= 1;
            } else if (direction == 2) {
                x -= 1;
            } else {
                y += 1;
            }
            if (x >= 0 && y >= 0 && x < location.length && y < location.length) {
                location[x][y] = true;
            } else
                break;
        }
    }

    private static void findDirection(int g, ArrayList<Integer> directions) {
        for (int i = directions.size() - 1; i >= 0; i--) {
            directions.add((directions.get(i) + 1) % 4);
        }
        if (g > 1)
            findDirection(g - 1, directions);
    }


    private static int countingSquare(boolean[][] location) {
        int[] dx = {0, 0, 1, 1};
        int[] dy = {0, 1, 0, 1};
        int count = 0;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                int k = 0;
                for (; k < 4; k++) {
                    if (!location[i + dx[k]][j + dy[k]])
                        break;
                }
                if (k == 4)
                    count++;
            }
        }
        return count;
    }
}

 

시간복잡도

선을 긋는 횟수는 그래프의 세대와 관련이 있습니다.

0세대의 경우 1회

1세대의 경우 2회

2세대의 경우 4회

3세대의 경우 8회

n세대의 경우 $2^ n$회가 될 것입니다.

 

따라서 시간 복잡도는 $O(2^g)$가 됩니다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)