[SIM] 8911번 거북이

8911번 거북이

 

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

 

문제

상근이는 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다.

1. F: 한 눈금 앞으로
2. B: 한 눈금 뒤로
3. L: 왼쪽으로 90도 회전
4. R: 오른쪽으로 90도 회전

L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 명령을 나열한 것을 거북이 로봇의 컨트롤 프로그램이라고 한다.

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

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

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

 

입력

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

 

출력

각 테스트 케이스에 대해서, 거북이가 이동한 영역을 모두 포함하는 가장 작은 직사각형의 넓이를 출력한다.

 

예제 입력

3
FFLF
FFRRFF
FFFBBBRFFFBBB

 

예제 출력

2
0
9

 

해결방법

조건대로 구현하는 시뮬레이션 문제이다

또한 시뮬레이션을 하기 위한 도구로 queue 를 사용했다

 

 

⭐️ 솔루션 ⭐️

문제의 좌표를 행렬로 변환하여 생각하고 넓이를 구하는 것만 생각하면 별로 어렵지 않은 문제였다

명령을 입력받은 뒤, 각 명령을 실행한다

이 때, 명령을 실행하여 이동하는 것은 구조체를 통한 BFS 탐색으로 수행하였다

 

처음에는 2차원 배열을 통해 이동하는 노드를 체크해줬지만 문제를 풀다 이 과정이 불필요하다고 느꼈다

넓이를 구하기 위해서는 x좌표 와 y좌표 의 최소 좌표, 최대 좌표만 알고있으면 됐기 때문이다

따라서 각 탐색마다 최소, 최대를 갱신하여 이를 해결했다

 

 

 

소스코드

문제 해결 시간 : 40m

메모리 : 1991 KB

시간 : 68 ms

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct node {
    int x,y,dir,cnt;
    
    node() { }
    node(int _x,int _y,int _dir,int _cnt) : x(_x),y(_y),dir(_dir),cnt(_cnt) { }
};

int testcase;
int ans;
int lx,ly,hx,hy;

int dx[5] = {0,0,0,1,-1};
int dy[5] = {0,1,-1,0,0};

string command;

// x좌표와 y좌표의 최소,최대를 갱신함
void setPos(int x,int y){
    lx = min(lx,x);
    ly = min(ly,y);
    hx = max(hx,x);
    hy = max(hy,y);
}

// 후진
int reverse(int dir){
    if(dir == 1) return 2;
    else if(dir == 2) return 1;
    else if(dir == 3) return 4;
    else return 3;
}

// 왼쪽으로 90도 회전
int turnLeft(int dir){
    if(dir == 1) return 4;
    else if(dir == 4) return 2;
    else if(dir == 2) return 3;
    else return 1;
}

// 오른쪽으로 90도 회전
int turnRight(int dir){
    if(dir == 1) return 3;
    else if(dir == 3) return 2;
    else if(dir == 2) return 4;
    else return 1;
}

void go(int r,int c){
    queue<node> q;
    q.push(node(r,c,4,0));
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        int cnt = q.front().cnt;
        q.pop();
        
        // 다음 명령어
        char nxt = command[cnt];
        
        switch (nxt) {
            case 'F':{
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                q.push(node(nx,ny,dir,cnt+1));
                setPos(nx,ny);
                break;
            }
                
            case 'B':{
                int nd = reverse(dir);
                int nx = x + dx[nd];
                int ny = y + dy[nd];
                q.push(node(nx,ny,dir,cnt+1));
                setPos(nx,ny);
                break;
            }
            
            case 'L':{
                int nd = turnLeft(dir);
                q.push(node(x,y,nd,cnt+1));
                break;
            }
                
            case 'R':{
                int nd = turnRight(dir);
                q.push(node(x,y,nd,cnt+1));
                break;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=0; t<testcase; t++){
        cin >> command;
        
        // x좌표와 y좌표의 최소,최대값은 현재 거북이의 좌표
        lx = 250;
        ly = 250;
        hx = 250;
        hy = 250;
        
        go(250,250);
        
        cout << abs(hx-lx) * abs(hy-ly) << "\n";
    }
    
    return 0;
}