11/19 미궁 속의 방

삼성 코드그라운드에서 제공하는 알고리즘에 관한 개인적인 풀이를 정리했습니다.

아래 사이트에서 직접 풀어보실 수 있습니다.

 

https://www.codeground.org/practice

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

 

이 문제를 처음 봤을때는 전처리를 통해서 미리 맵을 저장 해놓고, 좌표에 따라서 답을 계산하면 될 거라고 생각했다. 하지만 N이 최대 100000까지 들어올 수 있어서 미리 맵을 저장 하면 메모리 제한을 넘어가는 경우가 생겼고, 따라서 다른 방법을 찾아야 했다. 

 

 

문제를 해결하기 위해 좌표를 만져보던 중, 첫 번째 방을 좌표 (0, 0) 으로 해서 2, 3번째 방을 각각 좌표 (0, 1), (1, 0), 4, 5, 6번째 방을 각각 좌표 (2, 0), (1, 1), (0, 2)으로 생각하면 각 방의 x좌표와 y좌표를 더한 값 (pointSum)으로 그 방이 몇 번째 대각선에 속하는지 알 수 있다는 사실을 발견했다. 이를 이용하기 위해 먼저 변수 base에 1을 넣고, 아래나 오른쪽으로 움직일 때마다 pointSum 값을 더해주거나 빼주어 현재 속한 대각선 위쪽 방들의 번호 중 최댓값을 base에 저장하도록 했다. 

 

 

pointSum값이 홀수인지 짝수인지에 따라 현재 방 번호를 구하는 방법도 달라지는데, pointSum값이 홀수이면 대각선 위쪽에서 아래쪽으로 값이 증가하고, 짝수이면 대각선 아래쪽에서 위쪽으로 증가한다.

N=5인 미궁의 모습. 화살표 방향대로 방 번호가 증가한다.

 

이동 방향이 아래나 오른쪽이면 rd값을 1로, 위나 오른쪽이면 0으로 설정하고 각 이동에 맞게 좌표를 수정한 뒤 rd값에 따라 1이면 base에 pointSum을 더하고, 0이면 pointSum+1을 빼서 base값을 수정했다. ( rd값이 0일 때 pointSum+1을 빼는 이유는 아래나 오른쪽으로 이동할 때 base에 더한 pointSum 값을 위나 왼쪽으로 이동할 때 빼줘야 하는데, 위나 왼쪽으로 이동하면 pointSum값이 1 작아지기 때문에 이를 맞춰주기 위해서이다. ) pointSum이 홀수인지 짝수인지를 판별하여 짝수이면 현재 방 번호를 base+y+1로, 홀수이면 base+x+1로 구할 수 있었다. 

 

 

 

하지만 이것만으로는 제대로 된 값을 구할 수 없었는데, 이는 미궁의 아래쪽 부분에서는 대각선의 길이가 점점 짧아지기 때문에 base값이 제대로 업데이트 되지 않기 때문이었다.

미궁의 아랫 부분. 대각선의 길이가 아래로 갈수록 짧아진다.

 

이를 해결하기 위해서 pointSum값이 n을 넘어가는지 확인했고, 넘어갔을 때는 미궁의 아랫 부분에 해당한다는 의미이므로 base 값을 윗부분과 다르게 rd값이 1이면 base에 2*n-pointSum을 더하고, 0이면 base에서 2*n-(pointSum+1)을 빼도록 업데이트했다. 방 번호를 구할 때도 윗부분과는 다르게 구했는데, 윗부분은 모든 대각선이 y=0인 방(1, 3, 4, 10 ,11)을 가지고 있지만 아랫부분은 모든 대각선이 y=n-1인 방(16, 22, 23, 25)을 가지고 있으므로 이를 기준으로 구해서 pointSum이 홀수일 때는 base+n-x로, 짝수일 때는 base+n-y로 방 번호를 구할 수 있었다.

 

 

전체 코드는 다음과 같다.

#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
	int i, T, test_case;
	cin >> T;

	for (test_case = 0; test_case < T; test_case++)
	{
		int n, k;
		cin >> n >> k;
		char tmp[300000]; // direction 저장용
		cin >> tmp;
		int x = 0, y = 0; //초기 위치
		int rd = -1, base = 0; // ud : 아래나 오른쪽으로 이동할 때 1, 위나 왼쪽으로 이동할 때 0
		long long Answer = 1; //초기 위치 1번은 무조건 포함된다.
		for (i = 0; i < k; i++) {
			switch (tmp[i]) {
			case 'U':
				x--;
				rd = 0;
				break;

			case 'D':
				x++;
				rd = 1;
				break;

			case 'L':
				y--;
				rd = 0;
				break;

			case 'R':
				y++;
				rd = 1;
				break;
			}
			int pointSum = x + y; //udlr : 현재 위치가 왼쪽 아래에서 오른쪽 위로 가는 대각선들 중 몇 번째인지를 확인한다.
			if (pointSum < n) { //위쪽 삼각형
				if (rd) base += pointSum; //base : 구하는 대각선 윗부분의 방 번호 중 최댓값
				else base -= pointSum + 1;
				if (pointSum % 2 == 0) Answer += base + y + 1;
				else Answer += base + x + 1;
			}
		
			else { //아래쪽 삼각형
				if (rd) base += 2 * n - pointSum;
				else base -= 2 * n - (pointSum + 1);
				if (pointSum % 2 == 0) Answer += base + n - x;
				else Answer += base + n - y;
			}
		}
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}