[ 백준 ] 8911 / 거북이

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
100/228
post-thumbnail

# Appreciation

/*
 * Problem :: 8911 / 거북이
 *
 * Kind :: Simulation
 *
 * Insight
 * - 앞뒤로 움직이거나 방향을 바꾸는 것을 구현하는 건 그리 어렵지 않다...
 *   문제는 거북이가 지나간 영역을 모두 포함하는 정사각형의 넓이를 어떻게 알아내지...?
 *   + 한 (bool) Map[1000][1000] 정도로 두고
 *     (500,500) 에서 출발시켜 지나간 영역을 모두 체크한다음
 *     가장 왼쪽 위와 아래 칸의 좌표, 가장 오른쪽 위와 아래 칸의 좌표를 구해서
 *     너비와 높이를 구하기...?
 *     근데 방법이 너무 무식하다...
 *     # 직사각형의 정보를 모두 담는데는 두 좌표만 있으면 된다
 *       왼쪽 아래의 좌표와 오른쪽 위의 좌표 (왼쪽 위와 오른쪽 아래의 좌표도 가능)
 *       이 둘을 항상 추적할수... 있겠다!
 *       거북이가 움직일 때마다 왼쪽 아래의 좌표와 오른쪽 위의 좌표를 갱신시켜주면 된다!
 *       -> 프로그램이 끝나면
 *          각 좌표들을 통해 너비와 높이를 구해서 넓이를 구할 수 있다!
 */

# Code

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

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
enum { S, E, W, N };
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};
enum { L, R };
int cd[4][2] = {
        {E, W}, /* S */
        {N, S}, /* E */
        {S, N}, /* W */
        {W, E}  /* N */
};

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


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

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        string P; cin >> P;

        // Process
        int cy = 0, cx = 0, dir = N; /* 거북이의 초기 y 좌표, x 좌표, 방향 */
        /* ll = lower left, ur = upper right */
        int lly, llx, ury, urx; /* lly = 직사각형의 왼쪽 아래의 y 좌표
                                 * llx = 직사각형의 왼쪽 아래의 x 좌표
                                 * ury = 직사각형의 오른쪽 위의 y 좌표
                                 * urx = 직사각형의 오른쪽 위의 x 좌표 */
        lly = ury = cy;
        llx = urx = cx;

        for (char cmd : P) {
            switch (cmd) {
                case 'F': /* 한 눈금 앞으로 */
                    cy += dy[dir];
                    cx += dx[dir];
                    break;
                case 'B': /* 한 눈금 뒤로 */
                    cy -= dy[dir];
                    cx -= dx[dir];
                    break;
                case 'L': /* 왼쪽으로 90도 회전 */
                    dir = cd[dir][L];
                    break;
                case 'R': /* 오른쪽으로 90도 회전 */
                    dir = cd[dir][R];
                    break;
                default:
                    throw invalid_argument("Invalid Command");
            }

            /* 현재 좌표를 기준으로 직사각형의 왼쪽 아래, 오른쪽 위 좌표 갱신 */
            lly = min(lly, cy);
            ury = max(ury, cy);
            llx = min(llx, cx);
            urx = max(urx, cx);
        }

        // Control : Output
        int w = urx - llx; /* 너비 */
        int h = ury - lly; /* 높이 */
        cout << w*h << endl;
    }
}

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

0개의 댓글