[그리디 알고리즘] 롤러코스터

예제 입력 1

3 3

5 1 3

2 4 8

1 1 2

예제 출력 1

RRDLLDRR

 

- 모든 칸을 방문하면 된다.

첫번째 경우는 행의 개수가 홀수일 때,

두번째 경우는 열의 개수가 홀수일 때이다. (다른 요소가 짝수여도 상관없음을 확인할 수 있다.)

- 그러나, 행/열의 개수가 짝수이면 1개 칸은 반드시 방문할 수 없다. 이는 체스판으로 증명 가능하다.

검정에서 출발하여 검정으로 가야만 하는데, 검정->흰색->검정->흰색-> ... -> 검정으로 도달하려면 반드시 1개의 흰색을 방문하지 못하게 된다. 따라서, 검은 칸이면서 + 가장 작은 수가 있는 칸을 방문하지 않으면 된다.

- 풀이

Step 1) 문제의 조건에 따라 시작점을 (0,0), 끝점을(R-1,C-1)로 잡는다. 시작점을 이동시키는데, 끝점도 같이 이동시켜서 경로를 구할 수 있다. 파란색이 최소값이라 방문하지 않을 점이라고 가정하자. 

: 시작점으로부터 2칸 아래 이내에 파란색 칸이 없다면, 아래와 같이 쭉 오른쪽 -> 아래 1칸 -> 쭉 왼쪽 -> 아래 1칸을 이동시킨다.

: 끝점으로부터 2칸 위 이내에 파란색 칸이 없다면, 시작점 이동 경로와 동일하게 다른 vector에 저장한다. 왜냐하면 실제로 끝점이 움직이는것이 아니고 시작점이 움직이는 방향을 저장하여야 하므로, 시작점과 동일하게 저장해 나간 후 나중에 뒤집어야 한다.

 

: 이를, 시작점과 끝점의 행의 위치 차이가 1을 초과할 때 동안 반복하면, 최종적으로 아래와 같은 상태가 된다.

 

- Step2) 열에 대해서도 처리한다.

: 시작점으로부터 2칸 우측 이내에 파란색 칸이 없다면, 아래와 같이 아래 한칸 -> 오른쪽 한칸 -> 위 한칸 -> 오른쪽 한칸 이동한다.

: 끝점으로부터 2칸 좌측 이내에 파란색 칸이 없다면, 시작점 이동 경로와 동일하게 다른 vector에 저장한다. 이유는 같다. (왜냐하면 실제로 끝점이 움직이는것이 아니고 시작점이 움직이는 방향을 저장하여야 하므로, 시작점과 동일하게 저장해 나간 후 나중에 뒤집어야 한다.)

: 이를, 시작점과 끝점의 열의 위치 차이가 1을 초과할 때 동안 반복하면, 최종적으로 2x2 상태가 된다. 이는 아래 두가지 케이스 중 한가지 이다.

Step3)

시작점의 행 = 최소점의 행이면 아래 -> 오른쪽 이동,

그렇지 않으면 오른쪽 -> 아래 이동하여 마친다.

그리고, 끝점의 이동경로를 저장한 vector를 모두 뒤집는다.

#include <stdio.h>

constexpr int MAX_SIZE = 1001;

int map[MAX_SIZE][MAX_SIZE];

int R, C;

class Point
{
public:
	int r;
	int c;

	Point() { r = c = 0; }
	Point(int r, int c) : r(r), c(c) {}
};

class vector
{
public:
	char data[MAX_SIZE * MAX_SIZE];
	int size;

	vector() { size = 0; }

	void push(char item)
	{
		data[size] = item;
		size++;
	}

	void reverseAll()
	{
		int i = 0;
		int j = size - 1;

		while (i < j)
		{
			char item = data[i];
			data[i] = data[j];
			data[j] = item;

			i++;
			j--;
		}
	}
};
vector path;
vector path2;

int main(void)
{
	Point minNumberPos;
	int minNumber = 1001;

	scanf("%d %d", &R, &C);

	for (register int i = 0; i < R; i++)
	{
		for (register int j = 0; j < C; j++)
		{
			scanf("%d", &map[i][j]);

			if (minNumber > map[i][j] && ((i+j)%2==1))
			{
				minNumber = map[i][j];
				minNumberPos.r = i;
				minNumberPos.c = j;
			}
		}
	}

	Point start;
	Point end(R - 1, C - 1);

	if (C % 2 == 1)
	{
		int nowCol = 0;

		while (nowCol < C-1)
		{
			if (nowCol % 2 == 0)
			{
				for (int i = 0; i < R - 1; i++) path.push('D');
				path.push('R');
			}
			else
			{
				for (int i = 0; i < R - 1; i++) path.push('U');
				path.push('R');
			}
			nowCol++;
		}

		for (int i = 0; i < R - 1; i++) path.push('D');
	}
	else if (R % 2 == 1)
	{
		int nowRow = 0;

		while (nowRow < R - 1)
		{
			if (nowRow % 2 == 0)
			{
				for (int i = 0; i < C - 1; i++) path.push('R');
				path.push('D');
			}
			else
			{
				for (int i = 0; i < C - 1; i++) path.push('L');
				path.push('D');
			}
			nowRow++;
		}

		for (int i = 0; i < C - 1; i++) path.push('R');
	}
	else
	{
		// step1.
		while (end.r - start.r > 1)
		{
			if (start.r/2 < minNumberPos.r/2)
			{
				for (int i = 0; i < C - 1; i++) path.push('R');
				path.push('D');
				for (int i = 0; i < C - 1; i++) path.push('L');
				path.push('D');
				start.r+=2;
			}
			if (end.r / 2 > minNumberPos.r / 2)
			{
				for (int i = 0; i < C - 1; i++) path2.push('R');
				path2.push('D');
				for (int i = 0; i < C - 1; i++) path2.push('L');
				path2.push('D');
				end.r -= 2;
			}
		}

		// step2.
		while (end.c - start.c > 1)
		{
			if (start.c / 2 < minNumberPos.c / 2)
			{
				path.push('D');
				path.push('R');
				path.push('U');
				path.push('R');
				start.c += 2;
			}
			if (end.c / 2 > minNumberPos.c / 2)
			{
				path2.push('D');
				path2.push('R');
				path2.push('U');
				path2.push('R');
				end.c -= 2;
			}
		}

		// step3.
		// A X
		// O B
		if (start.r == minNumberPos.r)
		{
			path.push('D');
			path.push('R');
		}
		// A O
		// X B
		else
		{
			path.push('R');
			path.push('D');
		}
	}

	if (path2.size > 0)
	{
		path2.reverseAll();

		for (register int i = 0; i < path2.size; i++)
			path.push(path2.data[i]);
	}

	for (register int i = 0; i < path.size; i++)
		printf("%c", path.data[i]);
	printf("\n");

	return 0;
}