[삼성 기출] 백준 15685번 드래곤 커브 풀이

| |
백준 온라인 저지 15685번 - 드래곤 커브 C++ 풀이 (삼성 SW 역량테스트 기출)


문제

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

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

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

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

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

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

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


입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

  • 0: x좌표가 증가하는 방향 (→)
  • 1: y좌표가 감소하는 방향 (↑)
  • 2: x좌표가 감소하는 방향 (←)
  • 3: y좌표가 증가하는 방향 (↓)


출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.


풀이

문제 카테고리는 구현 및 시뮬레이션이지만, 드래곤 커브의 특정 규칙을 찾아내는 것이 핵심인 문제였다. 드래곤 커브의 특징들 중 문제를 해결하는 열쇠는 다음과 같다.

다음 세대의 드래곤 커브는 온전히 이전 세대의 드래곤 커브로 인해 결정된다

그리고 다음으로 주목해야할 것은 드래곤 커브의 진행 방향이다. 얼핏보면 진행 방향에 아무런 패턴이 없어보이지만 위에서 언급한 드래곤 커브의 특징과 연관지어 생각해보면 다음과 같은 아이디어를 얻을 수 있다.

다음 진행 방향은 지금까지의 진행 방향만으로 결정할 수 있다

마지막으로 다음 세대의 드래곤 커브는 이전 세대의 드래곤 커브를 시계 방향으로 90도 회전시킨 후 끝 점에 붙인 것이라고 하였다. 따라서 최종적으로 다음과 같은 패턴을 파악할 수 있다.

다음 진행 방향은 이전에 진행해온 방향들에 대한 반시계 방향으로 90도 회전시킨 것들의 역순이다.

예를 들어 문제의 조건과 같이 [0, 1, 2 ,3] 이 각각 [→, ↑, ←, ↓] 이라고 하면 다음과 같다.

  • 0121의 다음세대: 0121에 각각 1을 더한 것의 역순을 이어붙인것 -> 01212321

구현같은 경우에는 지금까지 지나왔던 방향을 스택에 기록한 후, 스택에서 하나씩 꺼내면서 1을 더해준것들을 이어붙이면 쉽게 할 수 있다.


전체 코드

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
#include <iostream>
#include <stack>
using namespace std;

int N;
int board[101][101];
int dy[] = {0,-1,0,1};
int dx[] = {1,0,-1,0};

int countSquare() {
    int ret = 0;
    for(int i=0;i<100;i++)
        for(int j=0;j<100;j++)
            if(board[i][j] && board[i+1][j] && board[i][j+1] && board[i+1][j+1])
                ret++;
    return ret;
}

void curveDragon(int x, int y, int d, int g) {
    stack<int> log;

    // 0세대
    board[x][y]=1;
    x+=dx[d]; y+=dy[d];
    board[x][y]=1;
    log.push(d);

    while(g--) {
        stack<int> temp = log;
        while(!temp.empty()) {
            int d = temp.top() + 1;
            temp.pop();
            x+=dx[d%4]; y+=dy[d%4];
            board[x][y]=1;
            log.push(d);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N;
    while(N--) {
        int x,y,d,g; cin>>x>>y>>d>>g;
        curveDragon(x,y,d,g);
    }

    cout<<countSquare();

    return 0;
}
0%