백준 15685번 드래곤 커브 :: 마이구미

이 글은 백준 알고리즘 15685번 "드래곤 커브" 문제를 풀이한다.

삼성 SW 역량 테스트의 문제로 출제된 적이 있다.

시뮬레이션 문제로써, 난이도 있는 알고리즘을 요구하는 문제는 아니다.

15685번 드래곤 커브 - https://www.acmicpc.net/problem/15685

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

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

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

................................................................................................................................

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

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

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

문제는 시작 점, 시작 방향, 세대에 따라 드래곤 커브가 변형된다.

문제를 완벽히 이해하지 않더라도, 드래곤 커브는 규칙이 존재할 것 같다는 느낌을 받을 수 있다.

규칙을 찾기 위해서는, 직접 그려보거나 적어보면 된다.

즉, 시뮬레이션해보면 된다.

문제에서는 방향을 숫자로 표현하고 있다. 

→ - 0, ↑ - 1, ← - 2, ↓ - 3

문제에서 제시된 것처럼 방향이 0인 드래곤 커브를 세대별로 표현해보자.

이 때 방향이 아닌 숫자로 표현해본다.

숫자 표현은 규칙을 찾는데 좀 더 도움이 되고 명확해질 것이다.

0 세대 - 0
1 세대 - 0 1
2 세대 - 0 1 2 1
3 세대 - 0 1 2 1 2 3 2 1
4 세대 - 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

위처럼 표현한 정보만으로도 규칙을 찾을 수 있다.

다음 세대는 이전 세대의 역방향으로 +1 한 방향을 나타내게 된다.

또한 세대가 증가할 때, 공비가 2인 등비 수열인 것을 파악할 수 있다.

이것으로 배열의 크기를 추측 및 설정할 수 있다.

이를 바탕으로 방향별로 드래곤 커브를 0 ~ 10 세대를 셋팅할 수 있다.

int[][] pattern = new int[4][1024];

pattern[0][0] = 0;
pattern[1][0] = 1;
pattern[2][0] = 2;
pattern[3][0] = 3;

for (int k = 0; k < 4; k++) {
    for (int i = 1; i <= 10; i++) {
        int start = (int) Math.pow(2, i - 1);
        int end = (int) Math.pow(2, i);
        for (int j = start, l = 1; j < end; j++, l += 2) {
            pattern[k][j] = pattern[k][j - l] + 1 == 4 ? 0 : pattern[k][j - l] + 1;
        }
    }
}

위 코드는 가장 단순한 방법이자 시나리오대로 구현한 방식이다. 

더 간단한 방법으로, 양방향이 가능한 벡터나 리스트를 활용하면 쉽게 구현할 수 있다.

그 후, 입력값에 맞는 드래곤 커브를 그린다.

for (int i = 0; i < n; i++) {
    int x = sc.nextInt();
    int y = sc.nextInt();
    int d = sc.nextInt();
    int g = sc.nextInt();
    int end = (int) Math.pow(2, g);

    int currentX = x;
    int currentY = y;
    map[currentY][currentX] = true;

    for (int j = 0; j < end; j++) {
        if (pattern[d][j] == 0) {
            currentX += 1;
        } else if (pattern[d][j] == 1) {
            currentY -= 1;
        } else if (pattern[d][j] == 2) {
            currentX -= 1;
        } else {
            currentY += 1;
        }
        map[currentY][currentX] = true;
    }
}

그려진 드래곤 커브가 있는 맵을 탐색하여 정사각형을 확인하면 정답을 구할 수 있다.

for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
        if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) {
            cnt++;
        }
    }
}

단순 이중 반복문을 통해 네 꼭짓점이 드래곤 커브로 만들어졌는지 확인하면 된다.

주의할 점은 x, y 방향으로 벽에 도달했을 때는 탐색할 수 없다는 것이다.

Github - https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/15685.java

// → - 0, ↑ - 1, ← - 2, ↓ - 3
private void solve() {
    int n = sc.nextInt();
    int[][] pattern = new int[4][1024];
    boolean[][] map = new boolean[101][101];
 
    pattern[0][0] = 0;
    pattern[1][0] = 1;
    pattern[2][0] = 2;
    pattern[3][0] = 3;
 
    // 드래곤 커브 셋팅
    for (int k = 0; k < 4; k++) {
        for (int i = 1; i <= 10; i++) {
            int start = (int) Math.pow(2, i - 1);
            int end = (int) Math.pow(2, i);
            for (int j = start, l = 1; j < end; j++, l += 2) {
                pattern[k][j] = pattern[k][j - l] + 1 == 4 ? 0 : pattern[k][j - l] + 1;
            }
        }
    }
 
    // 드래곤 커브 그리기
    for (int i = 0; i < n; i++) {
        int x = sc.nextInt();
        int y = sc.nextInt();
        int d = sc.nextInt();
        int g = sc.nextInt();
        int end = (int) Math.pow(2, g);
 
        int currentX = x;
        int currentY = y;
        map[currentY][currentX] = true;
 
        for (int j = 0; j < end; j++) {
            if (pattern[d][j] == 0) {
                currentX += 1;
            } else if (pattern[d][j] == 1) {
                currentY -= 1;
            } else if (pattern[d][j] == 2) {
                currentX -= 1;
            } else {
                currentY += 1;
            }
            map[currentY][currentX] = true;
        }
    }
 
    // 맵 탐색
    int cnt = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) {
                cnt++;
            }
        }
    }
    System.out.println(cnt);
}