15685번

15685번 - 드래곤 커브

규칙을 명확하게 식으로 풀어내는데 어려움을 느꼈다.

그리고 주어진 문제에서 X,Y 좌표 값이 내가 평상시에 쓰던 값이랑 달라서 헷갈렸다.

규칙은 각각의 버전을 따로 나열해서 생각해보면 찾을 수 있다.

주어진 예시의 경우

버전 0일때

오른쪽

버전 1일때

오른쪽 - 위쪽

버전 2일때

오른쪽 - 위쪽 - 왼쪽 - 위쪽

버전 3일때

오른쪽 - 위쪽 - 왼쪽 - 위쪽 - 왼쪽 - 아래쪽 - 왼쪽 - 위쪽

빨간색의 경우는 이전의 버전을 그대로 따라오고, 파란색의 경우는 빨간색을 역순으로 보았을 때 왼쪽으로 90도로 움직인 것이라 볼 수 있다.

위쪽은(↑) 왼쪽으로(←) , 왼쪽은(←) 아래쪽으로(↓) ...

따라서 이에 맞게 change 함수를 구현하고 dx,dy 배열을 이용하여 문제를 풀 수 있다.

나는 vector 를 이용해서 dragon 함수를 이용했지만, Stack을 이용하여 문제를 풀 수 있다.

 

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
typedef struct {
    int x, y;
}Point;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };
int map[101][101];
int n, x, y, d, g, ans;
void dragon();
int change(int dir);
 
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> y >> x >> d >> g;
        dragon();
    }
 
    //4점이 다 드래곤 커브인 지점을 확인.
    for (int i = 0; i <= 99; i++)
        for (int j = 0; j <= 99; j++)
            if (map[i][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j] == 1 && map[i + 1][j + 1] == 1)
                ans++;
 
    cout << ans << endl;
 
    return 0;
}
 
void dragon()
{
    //드래곤 커브의 g가 0일때를 계산
    vector<int> v;
    map[x][y] = 1;
    x += dx[d];
    y += dy[d];
    map[x][y] = 1;
    v.push_back(d);
 
    //드래곤 커브의 g가 1 이상인 경우 계산.
    while (g--)
    {
        for (int i = v.size() - 1; i >= 0; i--)
        {
            int nd = change(v[i]);
            x += dx[nd];
            y += dy[nd];
            map[x][y] = 1;
            v.push_back(nd);
        }
    }
    
 
}
//90도로 돌리는 방법.
int change(int dir)
{
    return (dir + 1) % 4;
}