codeground 미궁속의 방

https://www.codeground.org/main.do

[ 해결방법 ]

N이 10만이기 때문에 10만 X 10만의 배열을 선언해서 탐색하면 안된다. 메모리가 넘칠뿐만 아니라 제시간에 탐색할 수도 없다.

대신, 좌표로 방번호를 구해야 한다. 좌표점을 가지고 어떻게 방번호를 알 수 있을까? 

이 방의 탐색방향은 대각선이다. 예를 들면, (3, 1), (2, 2), (3, 1) 순서대로 탐색한다. 재미있는 것은 탐색방향이 바뀌기 전까지 x + y의 값이 같다는 것이다. 앞의 예에서는 x + y가 4로 모두 같다. 이점을 적극 활용해서 문제를 풀면된다.

우선, 탐색 방향이 바뀌는 점들을 모두 배열에 저장해 놓는다. N이 5일 때, 터닝포인트는 1, 2, 4, 7, 11, 16, 20, 23, 25이다.

다음으로, U,D,L,R에 따라서 x, y를 구한다. x, y가 구해지면, 터닝 포인트를 구할 수 있다. (3, 2)의 경우는 터닝포인트 배열의 x + y - 1번째의 시작점을 고르면 된다. Turning[3 + 2 - 1] = 7이 (3, 2) 방의 탐색방향의 시작점이다.

마지막으로, (3, 2)가 시작점(7)으로부터 얼마나 떨어져 있는지 계산하면된다. 시작점들은 모두 바깥에 위치해있다는 점을 이용하면, 빠르게 계산해낼 수 있다.

[ 코드 ]

#include <iostream>
using namespace std;
int T, tmpT;
unsigned long long Turning[200000];
char dirs[300000];
void make_point(int n)
{
	int idx = 2, inc = 1;
	Turning[1] = 1;
	for (; inc < n; inc++, idx++)
		Turning[idx] = Turning[idx - 1] + inc;
	for (; inc > 1; inc--, idx++)
		Turning[idx] = Turning[idx - 1] + inc;
}
void Move(char dir, int* x, int* y)
{
	switch (dir)
	{
	case 'U':
		--(*y);
		break;
	case 'D':
		++(*y);
		break;
	case 'L':
		--(*x);
		break;
	case 'R':
		++(*x);
		break;
	}
}
unsigned long long SearchRoom(int n, int x, int y)
{
	int idx = x + y - 1;
	unsigned long long point = Turning[idx];
	if (idx % 2 == 0)
	{
		if (idx <= n)
			point += (y - 1);
		else
			point += (n - x);
	}
	else
	{
		if (idx <= n)
			point += (x - 1);
		else
			point += (n - y);
	}
	return point;
}
int main()
{
	cin >> T;
	tmpT = T;
	while (tmpT--)
	{
		int N, K, x = 1, y = 1;
		unsigned long long Total = 1;
		cin >> N >> K;
		cin >> dirs;
		make_point(N);
		for (int i = 0; i < K; i++)
		{
			unsigned long long room;
			Move(dirs[i], &x, &y);
			room = SearchRoom(N, x, y);
			//cout << "( " << x <<", " << y << "), 방번호 : " << room << endl;
			Total += room;
		}
		cout << "Case #" << T - tmpT << endl;
		cout << Total << endl;
	}
	return 0;
}