본문 바로가기

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

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

 

문제에서 가장 큰 힌트는
크기가 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

 
1
2
3
4
5
6
7
8
9
10
11
12
    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;
    }
cs

2. 꼭짓점 그리기

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

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

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

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
    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;
            }
        }
    }
cs

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
    private static int getNumberOfSquares() {
        int count = 0;
 
        for (int x = 0; x &lt; LENGTH-1; x++) {
            for (int y = 0; y &lt; LENGTH-1; y++) {
                if (map[x][y] && map[x + 1][y] && map[x][y + 1&& map[x + 1][y + 1])
                    count++;
            }
        }
 
        return count;
    }
cs

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

전체 코드

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;
    }
}
cs