Boj 2873) 롤러코스터

문제

백준 2873

설명

Constructive Proof 를 요구하는 상당한 관찰력을 요구하는 문제이다.

우선 칸의 가로 세로가 모두 짝수 크기가 아닌 경우는 지그재그로 움직일 경우 모든 칸을 지나갈 수 있다는 것을 쉽게 도출할 수 있다. 이때 가로 세로의 홀짝이 다른 경우 지그재그의 방향이 한쪽으로 한정됨에 주의하자.

문제는 가로 세로가 모두 짝수 크기의 경우이다. 결론부터 말하자면 체크판에서 대각선 끝을 하얀칸으로 할 때 검은 칸에서 가장 작은 보상을 가진 한칸을 제외하고 모두 지나가면 된다.

이에 대한 증명은 백준 풀이를 보자.

시간 복잡도

O(\(\mathrm{M}\log{\mathrm{M}}\))

• 이때 \(M\) 은 총 마블 수

코드

int r, c;
int arr[1001][1001];
string ans;

void OneLeft(int t_x, int t_y)
{
	int x = 0, y = 0;
	bool bRight = true;
	for (int i = 0, bR = true; i < r; i++, bR = !bR)
	{
		if (t_y == i || t_y == i + 1)  // 이번 줄에서 제외할 칸이 있으면 세로 2칸에 걸쳐 지그재그
		{
			bool th = true;
			if (!bR) t_x = c - t_x - 1;    // 편의상 Left 방향일 때 인덱스를 거꾸로 해줌
			for (int j = 0; j < c - 1; j++)
			{
				if (t_x != j) { cout << (th ? 'D' : 'U'); th = !th; }  // 제외할 칸의 x 와 같을 때 지그재그 스킵
				cout << (bR ? 'R' : 'L');
			}
			i++; // 2칸에 걸쳐서 지그재그 하므로 무조건
			if (th) cout << 'D'; // 위에서 U 갯수가 D 갯수보다 많으면 D 추가
		}
		else
		{
			for (int j = 0; j < c - 1; j++)
				cout << (bR ? 'R' : 'L');
		}
		if (i != r - 1) cout << 'D';
	}
}

void Solve()
{
	if (r % 2 == 0 && c % 2 == 0)
	{
		// 검은칸에서 최소점 찾아서 마크
		int min_v = 1e9; int target_x = -1, target_y = -1;
		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++)
				if ((i + j) & 0b1 && min_v > arr[i][j])
					target_x = j, target_y = i, min_v = arr[i][j];
		arr[target_y][target_x] = -2;
		
		OneLeft(target_x, target_y);
	}
	else {
		if (r % 2 == 0) // down up first
		{
			for (int i = 0, bD = true; i < c; i++, bD = !bD)
			{
				for (int j = 0; j < r - 1; j++)
					cout << (bD ? 'D' : 'U');
				if (i != c - 1) cout << 'R';
			}
		}
		else {  // right left first
			for (int i = 0, bR = true; i < r; i++, bR = !bR)
			{
				for (int j = 0; j < c - 1; j++)
					cout << (bR ? 'R' : 'L');
				if (i != r - 1) cout << 'D';
			}
		}
	}
}

int main(void)
{
	cin >> r >> c;

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			cin >> arr[i][j];
	Solve();
}