AlgorithmSW역량테스트

삼성 SW 역량테스트 백준 드래곤커브 15685

, , , ,

1. 문제 링크

삼성 SW 역량테스트 기출 백준 드래곤커브 15685

2. 문제 조건

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 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만 유효한 좌표이다.

2.1. 입력

첫째 줄에 드래곤 커브의 개수 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좌표가 증가하는 방향 (↓)

3. 컴퓨팅 사고

  • 드래곤 커브라는것은 세가지 속성을 갖고 있습니다. 좌표평면위에 X축은 → 방향, Y축은 ↓ 방향으로 나타내며 일단 문제의 정의를 정확히 파악해야하는 문제입니다.
  • 속성 3가지는 시작점(x,y), 시작방향(상하좌우), 세대(0~3세대)를 나타냅니다. 세대는 총 0,1,2,3세대까지 나타낼 수 있습니다.
  • 문제를 접근하였을때 끝점을 기준으로 좌표가 어떤식으로 규칙을 띄고 있는지를 확인하였습니다. 하지만 제대로된 규칙을 찾을 수 없었습니다. 결국 상하좌우의 방향에 따라서 규칙성을 찾아보면 어떨까라는 생각을 하게 되었습니다.

세대의 규칙

0세대: 0

1세대: 0 1

2세대: 0 1 2 1

3세대 0 1 2 1 2 3 2 1

세대의 규칙을 찾으셨나요? 세대의 규칙을 찾은 방법에 대해 말씀드리겠습니다. 말그대로 시작점으로 부터 시작방향을 따라서 어떤 방향으로 이동하는지만 알면 됩니다.

0세대 같은 경우는 자기 자신(시작점)을 뜻합니다.

1세대 시작점에서 부터 오른쪽방향으로 움직입니다. 즉, 1(오른쪽)방향입니다.

2세대 0세대, 1세대를 거쳐서 왼쪽(2)→위(1)로 올라갑니다.

3세대 0세대, 1세대, 2세대를 거쳐서 왼쪽(2)→아래(3)→왼쪽(2)→위(1)의 방향으로 움직이게 됩니다.

이제 규칙을 발견하셨나요?

1세대→ 2세대가 움직이는 방향을 살펴보게 되면 01(1세대), 21(2세대)입니다. 자세히 살펴보면 01의 값을 역순을 해주면 10의 값이 됩니다. 여기에서 각각 +1씩 증가하면 21의 값이 되겠지요?

다음 차례인, 2세대 → 3세대의 값을 살펴보겠습니다. 2세대는 0121 방향으로 움직이게 됩니다. 이 값들을 역순을 하게되면 1210의 값이 되게 됩니다. 여기에서 값을 +1 시켜준다면 2321 의 방향으로 움직이는 규칙을 찾을 수 있습니다.

즉, 이전 세대 = (현재 세대의 역순의 방향을 모두 + 1)의 규칙을 찾을 수 있습니다.

세대별 방향 처리

dx, dy를 선언하여 아래와 같은 방향을 처리해주었습니다.

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

0~N세대의 방향을 저장시켜야 합니다.

이렇게 0세대부터 N세대까지로 이동하게 될때 세대의 방향값들을 저장시킬 하나의 저장소가 필요합니다. 저 같은 경우에는 vector를 사용하여 진행하였습니다.

격자위에 표시

0세대와 1세대는 첫 진입시 시작점을 하나의 격자위에 표시해주었습니다.

드래곤 커브 진행시 주의해야 할점

상하좌우의 값들을 진행시키기 위해서 0~3까지의 방향을 처리해야합니다. 0~3까지의 방향을 총 4개의 규칙적인 패턴을 처리하기 위해서는 어떻게 해야할까요? 나머지의 원리를 이용하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
i=0 
i % 4 = 0

i=1
i % 4 = 1

i=2
i % 4 = 2

i=3
i % 4 = 3

의 패턴을 가지게 됩니다. 만약 i가 4일경우는 나머지가 0이 되겠지요? 이렇게 계속 순서대로 패턴을 처리하면서 진행할 수 있습니다.

세대별로 처리하면서 방문한곳은 격자에 표시를 진행하면서 G번만큼의 드래곤 커브를 진행하게 됩니다.

사각형의 개수 구하기

G번만큼의 드래곤 커브를 진행하게 되면 격자위에 모든 세대들의 드래곤 커브가 완성되게 됩니다. 이제 모든 드래곤커브끼리 감싸고 있는 값들의 정사각형의 개수를 구하면 되겠지요?

정사각형의 개수를 구할때는 현재점을 (x, y)라고 지정하겠습니다.

정사각형이 되기위해서는 현재 자기자신(x,y) → (x+1,y) → (x,y+1) → (x+1,y+1)의 점들이 모두 격자에 표시되어야지 정사각형이 될 수 있습니다. 이렇게 표시된 점을 하나의 정사각형이라고 체킹을 할 수 있으며 이때 카운트변수를 하나 선언하여 return 해주게 된다면 최종적인 결과값을 구할 수 있게됩니다.

직접 그려보시면 평면좌표위에 어떻게 표시되는지 알 수 있을것입니다.

결론

좌표값으로 규칙을 찾으려고 하였는데 세대의 방향별 접근을 생각하지 못했습니다.

4. 소스 코드

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
//
//  드래곤커브.cpp
//  algorithm-ps
//
//  Created by kgh on 2020/09/16.
//  Copyright © 2020 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

const int MAX = 101;

int n = 0;
int x,y,d,g = 0;
int map[MAX][MAX];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
vector<int> dir_info;
void dragon_curve();
void sqaure_find();

// g세대까지 드래곤커브를 진행합니다.
void dragonCurve(){
    int size = dir_info.size();
    for(int i=size-1; i >= 0; i--){
        int nDir = (dir_info[i] + 1) % 4;
        x = x + dx[nDir];
        y = y + dy[nDir];
        map[x][y] = 1;
        
        dir_info.push_back(nDir);
    }
    
}
int sqaureFind(){
    int cnt = 0;
    
    for(int i=0; i<MAX; i++){
        for(int j=0; j<MAX; j++){
            
            if(map[i][j] == 1 && map[i+1][j] == 1 && map[i+1][j+1] == 1 && map[i][j+1] == 1){
                cnt++;
            }
        }
    }
    return cnt;
    
}

int main(void){
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> x >> y >> d >> g;
        
        // 맨 처음 시작지점 체크
        map[x][y] = 1;
        x = x + dx[d];
        y = y + dy[d];
        map[x][y] = 1;
        dir_info.clear();
        // 방향을 체크해서 저장시켜놔야지 나중에 역순+1을 시켜줄 수 있다.
        dir_info.push_back(d);
        // 다음 세대의 추가되는 선분의 방향정보 = 이전 세대의 방향정보를 역순으로 탐색하면서 + 1 % 4 를 한 것이 된다.
        for(int j=0; j<g; j++){
            // function dragon curve
            dragonCurve();
        }
    }
    int answer = sqaureFind();
    cout << answer << '\n';
    return 0;
}
Share