[BOJ] 백준 15685 드래곤 커브 c++ (구현, 시뮬레이션)

 

  문제

---

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

 

 

  풀이

---

가장 먼저 입력에 있는 인덱스 별 이동 방향을 잡아줬습니다. 처음에 dy를 {0, 1, 0, -1}로 했다가 한참 헤매버렸습니다.

int flat[101][101];

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

 

다음으로는 점을 그리는 함수를 만들었습니다. vector를 선언해서 세대별로 지나친 방향들을 저장했습니다. 1세대의 경우 0세대 까지 이동한 선을 90도 돌리고, 2세대의 경우 0, 1세대에 이동한 선을 90도 돌리고, 3세대의 경우 0, 1, 2세대에 이동한 선을 90도 돌리는 방식이기 때문에 쭉 기록하는 방식으로 구현했습니다.

 

0 -> 1

0 1 -> 2 1

0 1 2 1 -> 2 3 2 1

0 1 2 1 2 3 2 1 -> 2 3 0 3 2 3 2 1

 

0세대는 이전 값이 없어서 고정으로 넣어두고, 그 뒷 세대는 기록된 순서의 역순으로 90도를 돌려 이어서 저장을 해줬습니다. 문제의 규칙을 파악해 보면 n번째 세대의 경우 n-1번째 세대를 역순으로 90도 돌리면 완성됩니다. 그리고 진행하는 선의 끝 점의 경우 마지막 포인트를 기점으로 진행되기에 x_now, y_now를 선언해 진행했습니다. 

void draw(int x, int y, int d, int g)
{
    vector<int> v;
    v.push_back(d);
    
    int x_now = x + dx[d], y_now = y + dy[d];
    flat[y][x] = 1;
    flat[y_now][x_now] = 1;

    for (int i = 1; i <= g; i++)
    {
        for (int j = v.size() - 1; j >= 0; j--)
        {
            int tmp = (v[j] + 1) % 4;
            v.push_back(tmp);

            x_now += dx[tmp];
            y_now += dy[tmp];
            if (y_now >= 0 && y_now < 101 && x_now >= 0 && x_now < 101)
                flat[y_now][x_now] = 1;
        }
    }
}

 

문제의 출력은 점이 아닌 사각형이기에 그려진 flat을 통해 기준점을 바탕으로 4개의 점이 모두 1이면 카운트를 올려주는 식으로 정답을 구했습니다. 

for (int i = 0; i < 100; i++)
{
    for (int j = 0; j < 100; j++)
    {
        if (flat[i][j] == 1 && flat[i + 1][j] == 1 && flat[i][j + 1] == 1 && flat[i + 1][j + 1] == 1)
            cnt++;
    }
}

 

 

  전체 코드

---

#include <iostream>
#include <vector>
using namespace std;

int flat[101][101];

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

void draw(int x, int y, int d, int g)
{
    vector<int> v;
    v.push_back(d);
    int x_now = x + dx[d], y_now = y + dy[d];
    flat[y][x] = 1;
    flat[y_now][x_now] = 1;

    for (int i = 1; i <= g; i++)
    {
        for (int j = v.size() - 1; j >= 0; j--)
        {
            int tmp = (v[j] + 1) % 4;
            v.push_back(tmp);

            x_now += dx[tmp];
            y_now += dy[tmp];
            if (y_now >= 0 && y_now < 101 && x_now >= 0 && x_now < 101)
                flat[y_now][x_now] = 1;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        draw(x, y, d, g);
    }

    int cnt = 0;
    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            if (flat[i][j] == 1 && flat[i + 1][j] == 1 && flat[i][j + 1] == 1 && flat[i + 1][j + 1] == 1)
                cnt++;
        }
    }
    cout << cnt;

    return 0;
}

 

 

  평가

---

 

확실히 시뮬레이션/구현 문제가 상황에 맞춰야해서 만드는 맛이 좋네요