백준 15685 드래곤 커브 - [C/C++] 삼성 코딩테스트

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

15685번: 드래곤 커브

코드:

#include <iostream>
#include <cmath>
#include <vector>
#define fastio() ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
int N;
int map[222][222];
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};
vector<int> way[4];
void draw(int y, int x, int d, int c, int g) {
    if (c == g) return; 
    map[y][x] = 1;
    draw(y + dy[way[d][c]], x + dx[way[d][c]], d, c + 1, g);
}
int main() {
    fastio();
    cin >> N;
    for (int i = 0; i < 4; i++) {
        way[i].push_back(i); way[i].push_back((i + 1) % 4);
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= 1024; j *= 2) {
            for (int k = 0; k < j; k++) {
                way[i].push_back((way[i][k] + 2) % 4);
            }
            for (int k = j; k < j + j; k++) {
                way[i].push_back(way[i][k]);
            }
        }
    }
    int a, b, c, d; 
    for (int i = 0; i < N; i++) {
        cin >> a >> b >> c >> d;
        draw(111 + b, 111 + a, c, 0, pow(2, d) + 1);
    }
    int cnt = 0;
    for (int i = 0; i < 222; i++) {
        for (int j = 0; j < 222; j++) {
            if (map[i][j] and map[i][j + 1] and map[i + 1][j] and map[i + 1][j + 1]) cnt++;
        }
    }
    cout << cnt;
}
 

 

문제요약: 

특이한 규칙으로 나아가는 dfs를 방문한다. 그리고 어떠한 점의 아래 오른쪽 대각선을 방문 한 다면 count++해서 count를 출력한다

 

생각의 흐름:

드래곤 커브가 나아가는데 일정한 규칙이 있다 ->

n세대의 드래곤 커브는 총 2^n + 1개 만큼 방문한다 ->

직접 방향을 그려 본다->

 

화살표와 방향의 표시

 

 

 

n세대의 드래곤 커브는 0부터 2^(n  - 1)개의 방향을 뒤집고,

2^(n - 1)부터 2^n개까지의 방향을 그대로 가져온다 ->

 

규칙

 

for (int i = 0; i < 4; i++) {
   way[i].push_back(i); way[i].push_back((i + 1) % 4);
}
for (int i = 0; i < 4; i++) {
   for (int j = 1; j <= 1024; j *= 2) {
       for (int k = 0; k < j; k++) {
           way[i].push_back((way[i][k] + 2) % 4);
       }
       for (int k = j; k < j + j; k++) {
           way[i].push_back(way[i][k]);
       }
   }
}

 

 

 

 

 

 

 

 

 

->그래프를 dfs하고 개수를 센다.