백준 8911: 거북이(c++, 구현 & 시뮬레이션)

사용 언어	티어	시간 제한	메모리 제한
c++		1초	128MB

 

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

8911번: 거북이

 

#0 문제

상근이는 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다.
F: 한 눈금 앞으로
B: 한 눈금 뒤로
L: 왼쪽으로 90도 회전
R: 오른쪽으로 90도 회전
L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 명령을 나열한 것을 거북이 로봇의 컨트롤 프로그램이라고 한다.

상근이는 자신의 컨트롤 프로그램으로 거북이가 이동한 영역을 계산해보려고 한다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다. 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 프로그램을 작성하시오. 단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다.

아래 그림에서 거북이는 가장 처음에 (0, 0)에 있고, 북쪽을 쳐다보고 있다. 컨트롤 프로그램이 FLFRFLBRBLB인 경우에 거북이는 아래와 같이 움직인다. 회색으로 빗금친 부분이 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형이다. 넓이는 4가 된다.

거북이가 지나간 영역이 직사각형을 만들지 않는 경우도 있다. 예를 들어, FFLLFF인 경우에 거북이는 y축의 위로만 지나다닌다. 이 경우에 거북이가 지나간 영역을 모두 포함하는 직사각형은 선분이고, 선분은 한 변이 0인 직사각형으로 생각할 수 있다. 따라서, 선분의 경우에 넓이는 0이 된다.

 

#1 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 있고, 길이는 500을 넘지 않는다. 

 

#2 접근

• 간단한 구현 문제이다.
• 'L', 'R'의 경우에는 방향만 바뀜에 유의한다.
• 직사각형의 넓이를 계산하는 방법에 대해 고민해볼 필요가 있다.

 

#3 풀이

• 거북이가 북쪽을 보고 시작하므로 방향은 북, 동, 남, 서 순서로 배열을 만들었다.
• 'F'일 경우 앞이므로 방향을 유지하고, 방향에 해당하는 좌표만큼 이동한다.
• 'B'일 경우 뒤이므로 방향은 유지한채로 방향의 반대 방향에 해당하는 좌표만큼 이동한다. 반대 방향은 index 차이가 2이므로 (idx + 2) % 4로 구해주도록 한다. 이때 방향의 갱신은 이루어지지 않는다.
• 'L'일 경우 왼쪽으로 회전해야한다. 왼쪽 방향은 index가 1 작으므로 (idx + 3) % 4로 구해주고 방향을 갱신한다.
• 'R'일 경우 오른쪽으로 회전해야한다. 오른쪽 방향은 index가 1 더 크므로 (idx + 1) % 4로 구해주고 방향을 갱신한다.
• 새로운 좌표로 움직일 때마다, 방문한 좌표의 (x, y)값을 저장해주어야 나중에 직사각형의 크기를 구할 수 있다.
• 직사각형의 크기는 (가장 큰 x 좌표 - 가장 작은 x 좌표) * (가장 큰 y 좌표 - 가장 작은 y 좌표) 라고 말할 수 있다.
  • 이를 위해서 row, col에 해당하는 min, max heap을 각각 만들어주었다. 새로운 좌표를 방문할 때마다 힙을 갱신해준다.

#4 코드

/*
8911 거북이
구현
*/

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstdlib>

using namespace std;


// 방향을 북 동 남 서
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int dir;
int curX;
int curY;

// F이면 방향으로 감, B이면 방향 반대로 감(방향 반대는 (idx + 2) % 4)
// L이면 (idx + 3) % 4, R이면 (idx + 1) % 4

priority_queue<int, vector<int>, greater<int>> row_min;
priority_queue<int> row_max;
priority_queue<int, vector<int>, greater<int>> col_min;
priority_queue<int> col_max;



void update_value(int row, int col) {
    row_min.push(row);
    row_max.push(row);
    col_min.push(col);
    col_max.push(col);
}


void update_pos(int d) {
    curX += dx[d];
    curY += dy[d];
}



void move(char d) {
    if (d == 'F') {
        update_pos(dir);
        update_value(curX, curY);
    } else if (d == 'B') {
        update_pos((dir + 2) % 4);
        update_value(curX, curY);
    } else if (d == 'L') {
        dir = (dir + 3) % 4;
    } else if (d == 'R') {
        dir = (dir + 1) % 4;
    }
}


void init_tutle() {
    row_min = {};
    row_max = {};
    col_min = {};
    col_max = {};
    dir = 0;
    curX = 0;
    curY = 0;
    update_value(0, 0);
}

int run(string command) {
    init_tutle();
    for (int i = 0; i < command.size(); ++i) {
        move(command[i]);
    }
    int rowMin = row_min.top();
    int rowMax = row_max.top();
    int colMin = col_min.top();
    int colMax = col_max.top();
    int rowAbs = abs(rowMax - rowMin);
    int colAbs = abs(colMax - colMin);

    return rowAbs * colAbs;    
}

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


    int T;
    cin >> T;
    string command;

    for (int i = 0; i < T; ++i) {
        cin >> command;
        cout << run(command) << "\n";
    }


    return 0;
}