[백준] 15685. 드래곤 커브 - C++

문제

https://www.acmicpc.net/problem/15685

• 소요 시간 : 1시간
• 난이도 : 골드 3

접근 방법

구현/시뮬레이션 이다.

 

1. 드래곤 커브의 규칙을 찾는다.

 

드래곤 커브를 그려서 방향을 나열해보면 

 

0세대 : 0

1세대 : 0 1

2세대 : 0 1 2 1 

3세대 : 0 1 2 1 2 3 2 1 

...

 

n세대 : n-1세대 + (n-1세대 역순에 1씩 더한 것) 

이라는 것을 알 수 있다.

 

ex. 

1세대 : 0 1

2세대 : 0 1 1+1 0+1 = 0 1 2 1 

 

이러한 규칙을 바탕으로 드래곤 커브의 방향 정보들을 가지고 있는다.

 

2. 입력받은 시작점에서 위의 드래곤 커브의 방향 정보에 따라 움직이고 방문한 곳은 1로 변경한다.

3. 전체 맵을 돌면서 현재 점과 우, 우하, 하단의 점이 모두 방문했을 경우 개수를 +1 해준다.

 

나의 풀이

#include <iostream>
#include <vector>

using namespace std;

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

vector<int> makeDragonCurve(int dir, int generation) {
    vector<int> v; 
    v.push_back(dir);

    for(int i=0; i<generation; i++) {

        vector<int> new_v; 
        for(int j=v.size()-1; j>=0; j--) {
            int num = (v[j] + 1) % 4;
            new_v.push_back(num);
        }

        for(int j=0; j<new_v.size(); j++) {
            v.push_back(new_v[j]);
        }
    }

    return v;
}

bool check(int x, int y) {
    
    int checkDx[3] = {1, 1, 0};
    int checkDy[3] = {0, 1, 1};

    if (map[y][x]) {
        int cnt = 0;

        for(int i=0; i<3; i++) {
            int ny = y + checkDy[i];
            int nx = x + checkDx[i];

            if (ny < 0 || ny > 100 || nx < 0 || nx > 100) 
                continue;
            
            if (map[ny][nx]) cnt++;
        }
        return cnt == 3;
    }

    return false;
}

int main() {

    cin >> N;

    for(int i=0; i<N; i++) {
        int x, y, d, g; 
        cin >> x >> y >> d >> g;

        vector<int> dirInfo = makeDragonCurve(d, g);

        map[y][x] = 1;

        for(int i : dirInfo) {
            y = y + dy[i];
            x = x + dx[i];
            map[y][x] = 1;
        }
        
    }

    int answer = 0;

    for(int y=0; y<100; y++) {
        for(int x=0; x<100; x++) {
            // 우, 우하, 하 
            if (check(x, y)) answer++;
        }
    }

    cout << answer << "\n";


    return 0;
}

정리

처음에 직접 90도 회전시켜야 하는 줄 알고 .. 행렬 이런것들을 이용해야하나 했는데 규칙이 있었다. 

여러 시각에서 보는 연습을 해야겠다!

참고

https://yabmoons.tistory.com/60

[ 백준 15685 ] 드래곤 커브 (C++)