백준15685번: 드래곤 커브 자바 해설 (삼성 SW 역량 테스트 기출 문제)

• 문제 : https://www.acmicpc.net/problem/15685

정답은 맨 아래에 있습니다.

 

문제에서 가장 큰 힌트는
크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수
즉 변이 기준이 아닌 꼭짓점이 기준입니다. (문제에서 꼭짓점만 찾으면 된다는 거죠)

저는 3단계로 나눠서 풀었는데요.

1. 방향 구하기
2. 꼭짓점 그리기
3. 1×1인 정사각형 구하기

1. 방향 구하기

먼저 드래곤 커브의 방향을 구합니다. 무슨 말인지 문제에 나와 있는 예시의 그림으로 보여드리겠습니다.

아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽으로 3세대까지 그린 드래곤 커브입니다.

이 그림에서 화살표의 색깔이 다른 게 보이시나요?
세대가 증가할 때마다 이전의 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전해서 그립니다.
즉 이전의 세대의 방향을 바탕으로 그린다는 거죠.

같은 색의 화살표끼리는 짝인데요, 방향이 반시계로 바뀌는게 보이시나요?
그걸 바탕으로 입력받은 세대(g)까지 커브의 방향을 리스트에 담아줄 건데요

0: (→) x++
1: (↑) y--
2: (←) x--
3: (↓) y++

위에서 반시계로 바뀔때 1씩 증가합니다.
그리고 ↓(3) -> →(0) 는 3에서 0으로 바뀌죠.
(기존의 d + 1) % 4    ex) (3+1) % 4 = 0

 

    public static List<Integer> getDirections(int d, int g) {
        List<Integer> directions = new ArrayList<>(); // 방향을 담아줄 list 생성
        directions.add(d); // 초기 d 입력
 
        while (g-- > 0) { // g세대까지 반복
            for (int i = directions.size() - 1; i >= 0; i--) { // 마지막 방향 -> 처음방향까지 순서로 반복
                int direction = (directions.get(i) + 1) % 4; // (기존의 d+1)%4  
                directions.add(direction); // 새로운 방향 추가
            }
        }
        return directions;
    }

2. 꼭짓점 그리기

1번에서 구한 방향을 가지고 꼭짓점을 그리겠습니다.
먼저 각 꼭짓점을 그려줄 맵을 이중 배열로 선언할건데요.
조건에 (0 ≤ x, y ≤ 100)라고 나와있습니다. 즉 크기는 101입니다.
(알고리즘 문제를 풀 때는 조건을 잘 확인하는게 정말 중요합니다! 때로는 강력한 힌트가 될 수가 있습니다.)

private static boolean[][] map = new boolean[101][101];

그 다음 1번에서 구한 방향 list를 가지고 꼭짓점에 true로 체크해주겠습니다.
단순히 0,1,2,3으로 하면 직관적이지 않기 때문에 상수로 선언해주겠습니다.

    private static final int RIGHT = 0;
    private static final int UP = 1;
    private static final int LEFT = 2;
    private static final int DOWN = 3;
 
    public static void draw(int x, int y, List<Integer> directions) {
        map[x][y] = true;
 
        for (int direction : directions) {
            switch (direction) {
                case RIGHT:
                    map[++x][y] = true;
                    break;
                case UP:
                    map[x][--y] = true;
                    break;
                case LEFT:
                    map[--x][y] = true;
                    break;
                case DOWN:
                    map[x][++y] = true;
                    break;
            }
        }
    }

여기까지 꼭짓점까지는 그렸습니다.

3. 1 × 1인 정사각형 구하기

다시한번 말하지만 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수입니다.

 if (map[x][y] && map[x + 1][y] && map[x][y + 1] && map[x + 1][y + 1])

이 조건이 충족되면 정사각형이 되는거죠.

이제 이것을 어떻게 찾을지가 문제인데요. 저는 완전탐색을 사용했습니다.

    private static int getNumberOfSquares() {
        int count = 0;
 
        for (int x = 0; x < LENGTH-1; x++) {
            for (int y = 0; y < LENGTH-1; y++) {
                if (map[x][y] && map[x + 1][y] && map[x][y + 1] && map[x + 1][y + 1])
                    count++;
            }
        }
 
        return count;
    }

여기까지입니다. 도움이 되었으면 좋겠는데 설명이 어려워서 잘 이해가 되셨을지 모르겠네요..
혹시라도 댓글 남겨주시면 최대한 도움드리겠습니다.

전체 코드

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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

import java.util.ArrayList; import java.util.List; import java.util.Scanner;   public class Main {     private static final int RIGHT = 0;     private static final int UP = 1;     private static final int LEFT = 2;     private static final int DOWN = 3;     private static final int LENGTH = 101;       private static boolean[][] map = new boolean[LENGTH][LENGTH];       public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int N = sc.nextInt(); // 커브의 개수           while (N-- > 0) {             int x = sc.nextInt();             int y = sc.nextInt();             int d = sc.nextInt(); // 시작 방향             int g = sc.nextInt(); // 세대               draw(x, y, getDirections(d, g));         }           System.out.println(getNumberOfSquares());     }       public static List<Integer> getDirections(int d, int g) {         List<Integer> directions = new ArrayList<>();         directions.add(d);           while (g-- > 0) {             for (int i = directions.size() - 1; i >= 0; i--) {                 int direction = (directions.get(i) + 1) % 4;                 directions.add(direction);             }         }         return directions;     }       public static void draw(int x, int y, List<Integer> directions) {         map[x][y] = true;           for (int direction : directions) {             switch (direction) {                 case RIGHT:                     map[++x][y] = true;                     break;                 case UP:                     map[x][--y] = true;                     break;                 case LEFT:                     map[--x][y] = true;                     break;                 case DOWN:                     map[x][++y] = true;                     break;             }         }     }       private static int getNumberOfSquares() {         int count = 0;           for (int x = 0; x < LENGTH-1; x++) {             for (int y = 0; y < LENGTH-1; y++) {                 if (map[x][y] && map[x + 1][y] && map[x][y + 1] && map[x + 1][y + 1])                     count++;             }         }           return count;     } } Colored by Color Scripter

cs