[ 백준 ] 15685 / 드래곤 커브

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
42/228
post-thumbnail

# Appreciation

/*
 * Problem :: 15685 / 드래곤 커브
 *
 * Kind :: Simulation
 *
 * Insight
 * - 90도 회전이라...
 *  + 0: x좌표가 증가하는 방향 (→) / R
 *    1: y좌표가 감소하는 방향 (↑) / U
 *    2: x좌표가 감소하는 방향 (←) / L
 *    3: y좌표가 증가하는 방향 (↓) / D
 *    라고 하면
 *    # 문제 설명에서
 *      0세대 - R
 *      1세대 - RU
 *      2세대 - RULU
 *      3세대 - RULULDLU
 *      ...
 *      -> R 90도 회전 = U
 *         U 90도 회전 = L
 *         L 90도 회전 = D
 *         D 90도 회전 = R
 *         => 2세대 - RULU 에서
 *            U -> L
 *            L -> D
 *            U -> L
 *            R -> U
 *            3세대 - RULULDLU 는
 *            2세대 - RULU 에서
 *            각각의 방향에 대응하는 ULDL 을 뒤집어서 붙여주면 얻을 수 있다!
 *            드래콘 커브의 시작이 이전세대의 끝점이니까
 *            이전세대의 가장 마지막 방향이 다음세대의 첫번째 방향과 대응된다!
 *
 * Point
 * - R=0, U=1, L=2, D=3
 *   이고 90도 회전시 각각에 대응하는 방향이 순서대로
 *   U=1, L=2, D=3, R=0
 *   이니 각 방향의 숫자에 1을 더한후 4로 나눈 나머지를 구하면
 *   다음세대의 드래콘 커브를 쉽게 얻을 수 있다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
enum { R, U, L, D };
int dx[4] = {+1, 0, -1, 0};
int dy[4] = {0, -1, 0, +1};
int T[4] = {U, L, D, R};

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    bool A[100+1][100+1];
    memset(A, false, sizeof(A));
    for (int i=0; i<N; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;

        // Process
        A[x][y] = true; /* 시작점 */

        vector<int> D;
        D.push_back(d); /* 0세대 초기화 */
        for (int j=0; j<g; j++) {
            vector<int> tmp = D; /* 현재 세대 복사 */
            /* 복사한 현재 세대의 원소를 그 원소에 1을 더하고 4로 나눈 나머지로 바꾸어줌
             * 이는 각 원소에 해당하는 방향을 90도 회전시켜준 것을 뜻함 */
            for_each(tmp.begin(), tmp.end(), [](int &_d){ _d = (_d+1)%4; });
            /* 이후, 복사한 현재 세대 배열을 뒤집어 줌 */
            reverse(tmp.begin(), tmp.end());
            /* 이 배열을 원본 세대 배열의 뒤에 붙여줌으로써 다음 세대를 얻음 */
            move(tmp.begin(), tmp.end(), back_inserter(D));
        }
        /* 얻은 g세대 드래곤 커브의 방향 순서대로 점을 이동하며
         * 해당 점이 드래곤 커브의 일부임을 표시 */
        for (int _d : D) {
            x += dx[_d];
            y += dy[_d];
            A[x][y] = true;
        }
    }

    // Process
    int ans = 0; /* 크기가 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수 */
    for (int i=0; i<=99; i++) {
        for (int j=0; j<=99; j++) {
            /* 가능한 왼쪽위 정사각형의 좌표
             * x=0~99, y=0~99 */

            /* 왼쪽위 정사각형 좌표 기준 네 점이 모두 드래곤 커브의 일부라면 */
            if (A[i][j] && A[i+1][j] && A[i][j+1] && A[i+1][j+1]) {
                ans++;
            }
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글