• 백준 15685번 드래곤 커브 :: 마이구미
    알고리즘 풀이/수학 2018. 11. 17. 12:53
    반응형

    이 글은 백준 알고리즘 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    // → - 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] + == : 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);
    }
    cs


    반응형

    댓글 4

Designed by Tistory.