백준 BOJ 8911 - 거북이

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

8911번: 거북이

이동경로가 주어질때, 이동경로들을 모두 포함하는 가장 작은 직사각형의 넓이를 구하는 문제.

 

이 문제를 깔끔하게 풀기 위한 핵심으로써,

L과 R의 회전방향을 일관적으로 유지만 해준다면

거북이가 처음 쳐다보고 있는 방향은 아무런 관련이 없다는 것이다.

 

거북이가 만일 남쪽을 바라보고 있다고 하더라도,

그림에서 나온 평면을 180도 뒤집어서 시뮬레이션 가능하고,

이 경우에도 넓이는 같기 때문이다.

 

그런 관계로 내가 구현한 x,y가 지문에서 나오는 x,y와 서로 동일하지 않을 수 있다.

 

거북이가 지나간 영역을 모두 포함하는 직사각형은,

거북이가

양수 방향으로 간 가장 먼 x좌표 $mx_x$,

양수 방향으로 간 가장 먼 y좌표 $mx_y$,

음수 방향으로 간 가장 먼 x좌표 $mn_x$,

음수 방향으로 간 가장 먼 y좌표 $mn_y$

넷을 모두 포괄해야 하기 때문에,

 

가장 작은 직사각형의 넓이는

$(mx_x-mn_x) * (mx_y-mn_y)$ 이 된다.

 

#include <bits/stdc++.h>
using namespace std;

int mx_x = 0;
int mx_y = 0;
int mn_x = 0;
int mn_y = 0;
int dir = 0;
int x = 0;
int y = 0;

int main(){
	int N;
	cin >> N;
	while(N--){
		mx_x = mx_y = mn_x = mn_y = x = y = 0;
		dir = 1;
		
		string s;
		cin >> s;
		
		for(int i=0; i<s.length(); i++){
			if(s[i] == 'F'){
				switch(dir){
					case 1: x++; break;
					case 2: y++; break;
					case 3: x--; break;
					case 4: y--; break;
				}
			}
			
			if(s[i] == 'B'){
				switch(dir){
					case 1: x--; break;
					case 2: y--; break;
					case 3: x++; break;
					case 4: y++; break;
				}
			}
			
			if(s[i] == 'L'){
				dir++;
				if(dir == 5) dir = 1;
			}
			
			if(s[i] == 'R'){
				dir--;
				if(dir == 0) dir = 4;
			}
			
			mx_x = max(mx_x, x);
			mx_y = max(mx_y, y);
			mn_x = min(mn_x, x);
			mn_y = min(mn_y, y);
		}
		
		cout << (mx_x-mn_x) * (mx_y-mn_y) << "\n";
	}
}