[JAVA] 15685 - 드래곤 커브 💛3: 기하 문제라면 당황하지 말고 규칙을 찾아보자.

들어가며

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

세대별로 전 세대의 모양을 시계방향으로 돌려서 끝점에 붙혀가며 도형을 그렸을 때, 정사작형이 총 몇개 있는지 개수를 구하는 문제였다.

본문으로

처음 봤을 때 너무 막막했다. 이러한 기하 느낌의 문제를 풀어본 적이 많이 없었을 뿐더러 특히 문제에서 요구하는 세대별 변화를 좌표이동 값으로 나타내기가 너무 어려웠다.

좌표이동의 규칙이 뭐가 있을까??? 하고 계에에에에속 그려봤는데 뭔가 보이는 것 같으면서도? 너무 구현하기가 어려웠다...

 

결국 다른 분들의 힌트를 받아, 방향의 규칙을 찾고 좌표의 증감을 나타내라는 힌트를 받았다. 좌표이동의 규칙을 찾는 것이 아니라 방향의 변화 규칙을 찾으니 비교적 로직을 쉽게 구할 수가 있었다. 문제에서 0,1,2,3이 각각 x,y가 증감하는 값이라고 지정해준 값을 활용해서 방향 리스트를 만들어본다면,

0세대에서 시작 방향이 0이라면 방향 리스트는:

• 0

1세대는 기존 방향을 뒤에서부터 보면서 각각 +1 mod 4 해준 걸 뒤에 붙인다. 왜냐하면 시계 방향 90도 회전 = 방향 번호 +1 (mod 4) 이기 때문이다.

예를 들어:

0세대

[0]

1세대

기존 [0]을 뒤집어서 보면 [0],  각각 +1 → [1]
붙이면: [0, 1]

2세대

기존 [0, 1]을 뒤집으면 [1, 0], 각각 +1 → [2, 1]
붙이면: [0, 1, 2, 1]

3세대

기존 [0, 1, 2, 1]을 뒤집으면 [1, 2, 1, 0], 각각 +1 → [2, 3, 2, 1]
붙이면: [0, 1, 2, 1, 2, 3, 2, 1]

이 방향 리스트대로 점을 찍으면 드래곤 커브가 완성된다. 

즉 방향 리스트를 구해서 규칙대로 드래곤 커브를 그려준 다음 정사각형을 갯수를 카운팅 해주는 로직을 아래처럼 구성해볼 수가 있다.

public class Main {

    static boolean[][] visited = new boolean[101][101];

    // 방향: 0(→), 1(↑), 2(←), 3(↓)
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());

            drawDragonCurve(x, y, d, g);
        }

        int answer = countSquares();
        System.out.println(answer);
    }

    static void drawDragonCurve(int x, int y, int d, int g) {
        ArrayList<Integer> dirs = new ArrayList<>();
        dirs.add(d);

        // 세대 확장
        for (int gen = 1; gen <= g; gen++) {
            for (int i = dirs.size() - 1; i >= 0; i--) {
                dirs.add((dirs.get(i) + 1) % 4);
            }
        }

        // 시작점 표시
        visited[y][x] = true;

        // 방향대로 이동하며 점 표시
        for (int dir : dirs) {
            x += dx[dir];
            y += dy[dir];
            visited[y][x] = true;
        }
    }

    static int countSquares() {
        int count = 0;

        for (int y = 0; y < 100; y++) {
            for (int x = 0; x < 100; x++) {
                if (visited[y][x] &&
                        visited[y][x + 1] &&
                        visited[y + 1][x] &&
                        visited[y + 1][x + 1]) {
                    count++;
                }
            }
        }

        return count;
    }
}

마무리하며

알고리즘 대회가 아니라면, 기하 문제는 사실 기하 문제인 "척" 하는 규칙찾기 문제라고 많이들 부른다.

앞으로도 도형을 좌표상에서 다루는 문제가 나온다면 당황하지 말고, 하나씩 그려보며 규칙을 찾는 방법에 최선을 다하자!!