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

문제링크 : https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

vector<int>direction;
int dx[] = {1, 0, -1, 0}; //→, ↑, ←, ↓
int dy[] = {0, -1, 0, 1};
int x, y, d, g;
int arr[101][101];
int cnt = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    while(N--)
    {
        direction.clear();
        cin >> x >> y >> d >> g; //커브 시작 점, 시작 방향, 세대

        arr[x][y] = 1; //초기 값

        //0세대
        x += dx[d]; 
        y += dy[d]; 
        arr[x][y] = 1; //드래곤 커브 꼭짓점 표시
        direction.push_back(d);

        while(g--) //g세대 만큼 반복
        {
            int size = direction.size();
            for(int i=size-1; i>=0; i--)  //끝점에서 붙이기
            {
                int next_direction = (direction[i] + 1) % 4; //다음 방향
                x += dx[next_direction];
                y += dy[next_direction];
                arr[x][y]=1;
                direction.push_back(next_direction);
            }
        }
    }

    for(int i=0; i<101; i++)
    {
        for(int j=0; j<101; j++)
        {
            if(arr[i][j]==1 && arr[i][j+1]==1 && arr[i+1][j]==1 && arr[i+1][j+1] == 1) //사각형 꼭짓점이 전부 1이면
            {
                cnt++;
            }
        }
    }

    cout <<cnt;

    return 0;

}

구현문제이다.

커브가 움직이는 방향이 → ↑ ← ↓ 이렇게 4가지이다.

방향의 순서가 정해져있으므로, 방향 좌표를 담은 dx, dy 값을 설정할 때 주의해야 한다.

 

처음 x, y 값을 받고, 해당 방향만큼 이동한 dx[d], dx[y] 를 x, y에 더해주면서 갱신한다.

방향은 G세대 만큼 반복되므로 따로 벡터에 담아둔다.

 

끝 점을 기준으로 붙여나가기 때문에, G세대만큼 반복할때 끝 방향부터 하는 것에 주의해야 한다.

그리고 방향이 총 0, 1, 2, 3 이렇게 4가지 값을 가지므로 다음 방향값을 설정할 때 현재 방향에 1을 더하고 항상 %4를 해줘야 한다.

 

이렇게 만든 다음 방향은 마찬가지로 아까 방향을 저장했던 벡터에 같이 담아두고, 세대에 따라 계산해줄 때 사용된다.

각 좌표 x, y마다는 1로 표시를 해두고, 정사각형의 갯수 즉, 4군데 꼭짓점이 다 1일 때 카운트를 세준다.