[C++] 백준 8911번: 거북이

문제 링크

8911번: 거북이

문제 요약

거북이가 하는 일련의 동작들이 주어진다. 거북이는 앞뒤로 한칸 이동하거나 왼쪽 또는 오른쪽으로 90도 회전이 가능하다. 이때 거북이가 이동한 경로들을 모두 덮는 가장 작은 직사각형의 넓이를 구해야 한다.

접근 방법

최소의 직사각형은 결국 거북이의 위치를 행과 열로 정의했을 때, (행의 최댓값 - 최솟값)과 (열의 최댓값 - 최솟값)을 곱한 것과 같습니다. 따라서 구현을 해서 시뮬레이션을 돌려주고, 돌리는 과정에서 최댓값들과 최솟값들을 갱신한 다음에 마지막에 차를 곱해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

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

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;

	while (t--)
	{
		string str;
		cin >> str;

		int r = 0, c = 0, d = 0, rmax = 0, rmin = 0, cmax = 0, cmin = 0;

		for (auto& i : str)
		{
			switch (i)
			{
			case 'F':
				r += dir[d][0];
				c += dir[d][1];
				break;
			case 'B':
				r -= dir[d][0];
				c -= dir[d][1];
				break;
			case 'L':
				d = (d + 1) % 4;
				break;
			case 'R':
				d = ((d - 1) < 0 ? 3 : d - 1);
			}

			rmax = max(rmax, r);
			rmin = min(rmin, r);
			cmax = max(cmax, c);
			cmin = min(cmin, c);
		}

		cout << (rmax - rmin) * (cmax - cmin) << '\n';
	}

	return 0;
}