[BOJ 8911] 거북이

 2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8911 에서 채점할 수 있습니다.

풀이 )

1) 거북이가 거쳐간 모든 좌표들을 알 수 있다면,  직사각형의 크기는 (max_x-min_x) * (max_y-min_y) 로 구할 수 있습니다.

 (max_x = 거북이가 거쳐간 x 좌표중 최대값, min_x = 거북이가 거쳐간 x 좌표중 최소값, max_y, min_y 도 같은 식입니다.)

2) 이 문제와 같이 90도로 회전하면서 전진하는 상황은 아래의 배열을 선언하여 시뮬레이션할 수 있습니다.

// code by RiKang, weeklyps.com
int dx[4]={0, -1, 0, 1}; // 위쪽, 왼쪽, 아럐쪽, 오른쪽으로 1칸 갈 때 x좌표의 변화입니다.
int dy[4]={1, 0, -1, 0}; // 위쪽, 왼쪽, 아럐쪽, 오른쪽으로 1칸 갈 때 y좌표의 변화입니다.

 이런 배열을 선언하고, (위쪽일 때 direction = 0, 왼쪽일 때 direction = 1, 아래쪽일 때 direction = 2, 오른쪽일 때 direction = 3)이 되는 변수 direction을 관리해주면, x+=dx[direction]; y+=dy[direction]; 을 통해 1칸 전진을 표현할 수 있습니다.

3) 왼쪽으로 90도 회전, 오른쪽으로 90도 회전은 direction 을 변경해주면 가능합니다.

 왼쪽 회전 : direction = (direction+1)%4

 오른쪽 회전 : direction = (direction+3)%4

 direction = 0, 1, 2, 3 일 때를 각각 생각해보면 위와 같은 식으로 방향이 바뀜을 알 수 있습니다. 오른쪽 회전이 (direction-1)%4가 아닌 이유는 direction=0 일 경우에 문제가 되기 때문입니다.

2), 3)을 이용하여 거북이의 움직입을 따라가면서 min_x, max_x, min_y, max_y를 구해주면 해결할 수 있습니다.

 최종 코드 )

// code by RiKang, weeklyps.com
// 2011 ACM-ICPC Daejeon regional - L
// BOJ 8911 거북이
 
#include <bits/stdc++.h>
using namespace::std;
 
char in[505];
int dx[4]={0, -1, 0, 1}; // 위, 왼, 아, 오
int dy[4]={1, 0, -1, 0};
 
void solve(){
    int x, y;
    int min_x, min_y, max_x, max_y;
    x=y=min_x=min_y=max_x=max_y=0;
    
    int direction = 0;
 
    scanf("%s",in);
    int n = strlen(in);
    for(int i=0; i<n; i++){
        if(in[i]=='F'){
            x+=dx[direction];
            y+=dy[direction];
        }
        else if(in[i]=='B'){
            x-=dx[direction];
            y-=dy[direction];
        }
        else if(in[i]=='L'){
            direction = (direction+1)%4;
        }
        else{
            direction = (direction+3)%4;
        }
        min_x = min(x, min_x);
        min_y = min(y, min_y);
        max_x = max(x, max_x);
        max_y = max(y, max_y);
    }
    printf("%d\n",(max_x-min_x)*(max_y-min_y));
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}