백준 15685 드래곤 커브

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

15685번: 드래곤 커브

#include <iostream>
#include <vector>
#include <stack>

using namespace std;


//우상좌하 순
int ny[4]={0, -1, 0, 1};
int nx[4]={1, 0, -1, 0};


bool map[101][101];





int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int ans = 0;

    cin >> n;

    for (int N = 0; N < n; N++) {

        int x, y, d, g;
        vector<int> timestamp;
        stack<int> st;

        cin >> y >> x >> d >> g;

        map[x][y] = true;

        //0세대
        timestamp.push_back(d);
        st.push(d);

        //1세대부터 n세대까지
        for (int gen = 1; gen <= g; gen++) {

            while (!st.empty()) {
                int cur = st.top();
                st.pop();

                timestamp.push_back((cur + 1) % 4);

            }

            for (int i = 0; i < timestamp.size(); i++) {
                st.push(timestamp[i]);
            }

        }

        //해당 타임스탬프에 칠하기

        pair<int, int> cur = {x, y};
        for (int cnt = 0; cnt < timestamp.size(); cnt++) {
            map[cur.first + ny[timestamp[cnt]]][cur.second + nx[timestamp[cnt]]] = true;
            cur = {cur.first + ny[timestamp[cnt]], cur.second + nx[timestamp[cnt]]};
        }



    }



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


    cout << ans;

    return 0;
}

 

timestamp에는 앞으로 연결할 드래곤 커브의 방향을 저장한다.

 

입력 시 d는 (우 상 좌 하) 순으로 반시계 방향이다.

반면 드래곤 커브를 그릴 때는 시계 방향으로 그린 뒤 이어붙인다.

  

(아래 숫자는 ny, nx의 index임(우상좌하 순))

   0세대 : 0

   1세대 : 0 1

   2세대 : 0 1 2 1

   3세대 : 0 1 2 1 2 3 2 1

 

이는 규칙을 찾아보니 반시계방향으로 그린 후 역순으로 이어붙인 것과 같았다.

 

따라서 다음과 같은 방법으로 timestamp를 채웠다.

  1. timestamp를 모두 stack에 push한다.

  2. 이들을 하나씩 꺼내면서 timestamp에 저장한다.

  

위 과정을 세대의 수 만큼 반복하면 해당 드래곤 커브의 경로가 완성된다.

주어진 좌표에서 시작하여 해당 경로를 쫒아가면서 그리면 완성이다.

 

이후 map을 전수조사하면서 1*1의 정사각형의 개수를 세면 정답을 출력할 수 있다.