거북이   

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	3605	1936	1511	52.465%

문제

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

F: 한 눈금 앞으로

B: 한 눈금 뒤로

L: 왼쪽으로 90도 회전

R: 오른쪽으로 90도 회전

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

상근이는 자신의 컨트롤 프로그램으로 거북이가 이동한 영역을 계산해보려고 한다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다.

거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 프로그램을 작성하시오. 

단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다.

아래 그림에서 거북이는 가장 처음에 (0, 0)에 있고, 북쪽을 쳐다보고 있다. 컨트롤 프로그램이 FLFRFLBRBLB인 경우에 거북이는 아래와 같이 움직인다.

회색으로 빗금친 부분이 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형이다. 넓이는 4가 된다.

거북이가 지나간 영역이 직사각형을 만들지 않는 경우도 있다. 예를 들어, FFLLFF인 경우에 거북이는 y축의 위로만 지나다닌다.

이 경우에 거북이가 지나간 영역을 모두 포함하는 직사각형은 선분이고, 선분은 한 변이 0인 직사각형으로 생각할 수 있다.

따라서, 선분의 경우에 넓이는 0이 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다.

프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 있고, 길이는 500을 넘지 않는다. 

출력

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

예제 입력 1

3
FFLF
FFRRFF
FFFBBBRFFFBBB

예제 출력 1

2
0
9

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional – Daejeon 2011 L번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: djm03178, hist0613

알고리즘 분류

• 구현
• 시뮬레이션

---

거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형을 구하는 문제

거북이가 할 수 있는 행동

F: 한 눈금 앞으로

B: 한 눈금 뒤로

L: 왼쪽으로 90도 회전

R: 오른쪽으로 90도 회전

을 구현하는 것과 이 행동으로 나온 결과물로 영역을 모두 포함 할 수 있는 가장 작은 직사각형의 넓이를 구하면 될 것 같다.

명령어는 string 입력 받아서 처리할 예정

테스트 케이스들은 list에 넣어서 처리

#include <iostream>
#include <list>

using namespace std;

int T;

string tempString;

list<string> testCase;

void Initializtion()
{
	cin >> T;
	while (T > 0)
	{
		cin >> tempString;
		testCase.push_back(tempString);
		T--;
	}

}

// 거북이가 지나간 영역을 포함하는 가장 작은 직사각형 계산 함수
int SizeCalculation(string testcase)
{




	return 0;
}


int main()
{
	// 초기화
	Initializtion();
	 
	for (auto iter = testCase.begin(); iter != testCase.end(); iter++)
	{
		cout << SizeCalculation(*iter) << "\n";
	}

	return 0;
}

배열로 거북이가 취할 수 있는 행동을 정의

명령어에서 실제로 좌표가 움직이는 명령은 F B

나머지 명령어는 거북이의 conditionTurtle를 변경해 준다.

직사각형의 넓이는 Set<int>를 이용하여 최소값과 최대값을 구하여 해결

통과된 코드

#include <iostream>
#include <list>
#include <set>

using namespace std;

int T;

string tempString;

list<string> testCase;

int directionTurtle[4][2] = {
	{0, 1 },
	{1, 0 },
	{0, -1},
	{-1, 0}
};

// 초기화
void Initializtion()
{
	cin >> T;
	while (T > 0)
	{
		cin >> tempString;
		testCase.push_back(tempString);
		T--;
	}

}

// 거북이가 지나간 영역을 포함하는 가장 작은 직사각형 계산 함수 
int SizeCalculation(string testcase)
{
	int curX = 0;
	int curY = 0;
	int conditionTurtle = 0;
	set<int> xSet;
	set<int> ySet;
	xSet.insert(curX);
	ySet.insert(curY);

	// 명령어를 처리하는 부분
	for (int i = 0; i < testcase.size(); i++)
	{
		switch (testcase[i])
		{
			case 'F': // 전진
				curX += directionTurtle[conditionTurtle][0];
				curY += directionTurtle[conditionTurtle][1];
				break;

			case 'B': // 후진
				curX -= directionTurtle[conditionTurtle][0];
				curY -= directionTurtle[conditionTurtle][1];
				break;

			case 'L': // 왼쪽으로 90도 회전
				conditionTurtle--;
				if (conditionTurtle <= -1) {
					conditionTurtle = 3; }
				break;

			case 'R': // 우측으로 90도 회전
				conditionTurtle++;
				if (conditionTurtle >= 4) {
					conditionTurtle = 0; }
				break;

			default:
				cout << "이거 나오면 큰일남";
				break;
		}

		xSet.insert(curX);
		ySet.insert(curY);
	}

	// Set<int>를 이용하여 x,y의 가장 낮은 값과 높은 값을 계산하여 직사각형 가로 세로를 구한다.
	int width = *xSet.begin() - *--xSet.end();
	int height = *ySet.begin() - *--ySet.end();

	return abs(width * height);
}


int main()
{
	Initializtion();
	 
	//테스트 케이스 만큼 반복
	for (auto iter = testCase.begin(); iter != testCase.end(); iter++)
	{
		cout << SizeCalculation(*iter) << "\n";
	}

	return 0;
}