[백준][구현] 15685 드래곤 커브 c++구현

목차

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

문제

 

문제 구현 방향

각 드래곤의 방향을 구한뒤 맵과 벡터에 좌표를 넣고 탐색하는 식으로 구현했다.

 

문제 아이디어

 

1. 드래곤의 방향을 넣고 좌표 구하기

드래곤의 움직임은 결국 방향벡터의 size만큼 세대별로 거꾸로 탐색해 방향벡터+1을 더한 값을 넣어주면 된다.

void dragonMoving() {
    vector<int> direct;
    for (int i = 0; i < v.size(); i++) {
        direct.clear();
        int generation = v[i].g;
        direct.push_back(v[i].d);

        while (generation) {
            generation--;
            int size = direct.size();
            for (int j = size-1; j >= 0; j--) {
                direct.push_back((direct[j] + 1) % 4);
            }
        }

        int sx = v[i].x;
        int sy = v[i].y;
        
        if (!m[{sx, sy}])
             dragons.push_back({ sx, sy });
        m[{sx, sy}] = 1;
        for (int j = 0; j < direct.size(); j++) {
            sx += dx[direct[j]];
            sy += dy[direct[j]];
            if(!m[{sx, sy}])
                dragons.push_back({ sx, sy });
            m[{sx, sy}] = 1;
        }
    }
}

 

 

2. 사각형 개수 구하기

각 좌표에서 사각형이 되는지 한 방향만 모두 탐색해 보면 된다.

void findRec() {
    for (int i = 0; i < dragons.size(); i++) {
        int cnt = 0;
        int sx = dragons[i].first;
        int sy = dragons[i].second;
        for (int j = 0; j < 3; j++) {
            int nx = sx + rx[j];
            int ny = sy + ry[j];
            if (m[{nx, ny}])
                cnt++;
       }
        if (cnt == 3)
            total++;
        cnt = 0;
    }
}

 

코드 구현

#include <iostream>
#include <vector>
#include<map>

using namespace std;

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


int rx[3] = { 1, 1, 0 };
int ry[3] = { 0, 1, 1 };

typedef struct dragon {
    int x;
    int y;
    int d;
    int g;
}dragon;

vector<dragon> v;
map<pair<int,int>, int> m;
vector<pair<int, int>> dragons;

int total = 0;
                     
//드래곤 좌표 탐색
void dragonMoving() {
    vector<int> direct;
    for (int i = 0; i < v.size(); i++) {
        direct.clear();
        int generation = v[i].g;
        direct.push_back(v[i].d);

        while (generation) {
            generation--;
            int size = direct.size();
            for (int j = size-1; j >= 0; j--) {
                direct.push_back((direct[j] + 1) % 4);
            }
        }

        int sx = v[i].x;
        int sy = v[i].y;
        
        if (!m[{sx, sy}])
             dragons.push_back({ sx, sy });
        m[{sx, sy}] = 1;
        for (int j = 0; j < direct.size(); j++) {
            sx += dx[direct[j]];
            sy += dy[direct[j]];
            if(!m[{sx, sy}])
                dragons.push_back({ sx, sy });
            m[{sx, sy}] = 1;
        }
    }
}

//사각형 탐색
void findRec() {
    for (int i = 0; i < dragons.size(); i++) {
        int cnt = 0;
        int sx = dragons[i].first;
        int sy = dragons[i].second;
        for (int j = 0; j < 3; j++) {
            int nx = sx + rx[j];
            int ny = sy + ry[j];
            if (m[{nx, ny}])
                cnt++;
       }
        if (cnt == 3)
            total++;
        cnt = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int x, y, d, g, N;
    cin >> N;

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

    dragonMoving();
    findRec();
    cout << total;

    return 0;
}