BOJ 2873 롤러코스터

출처 : https://www.acmicpc.net/problem/2873

사용한 알고리즘

그리디 알고리즘

알고리즘 설명

보드의 좌표중 하나라도 홀수가 있다면 롤러코스터는 모든 지점을 갈 수 있다.
둘다 홀수가 아닌 짝수인 경우 롤러코스터는 적어도 한 좌표를 포기해야한다. 이 좌표는 체스판의 흑백 좌표와 같은 형태로 x와 y축 좌표 합이 홀수인 경우이다.
위와 같이 두 좌표 합이 홀수 인 좌표중 가장 작은 값을 찾는다.
이 작은 좌표를 피해가는 롤러코스터 좌표를 찾아 출력한다.

풀이

// baekjoon 2873 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=1001;
const int MAX_D=4;
const int dir[4][2] = {{0,1}, {1,0}, {0, 1}, {-1, 0}};
const char dir_c[6] = "RDRU\0";
int R, C, x, ret=1e9, sx, sy, cx, cy, nx, ny, pos;
char ans[4001], p0[MAX_N], p1[MAX_N];

int main() {
	scanf("%d%d", &R, &C);
// 세로가 홀수 인 경우
	if (R % 2) {
		for (int j=0; j<C-1; j++) {
			p0[j]='L';
			p1[j]='R';
		}
		for (int i=0; i<R; i++) {
			if (i%2) printf("%s", p0);
			else printf("%s", p1);
			if (i!=R-1) printf("D");
		}
	}
// 가로가 홀수 인 경우
  else if (C % 2) {
		for (int j=0; j<R-1; j++) {
			p0[j]='U';
			p1[j]='D';
		}
		for (int i=0; i<C; i++) {
			if (i%2) printf("%s", p0);
			else printf("%s", p1);
			if (i!=C-1) printf("R");
		}
	}
// 가로 세로 모두 짝수인 경우
  else {
		for (int j=0; j<C-1; j++) {
			p0[j]='L';
			p1[j]='R';
		}
// 가장 작은 지점 찾기
		for (int i=0; i<R; i++) {
			for (int j=0; j<C; j++) {
				scanf("%d", &x);
				if ((i+j)%2 && x < ret) ret = x, sx=i, sy=j;
			}
		}
		for (int i=0; i<R/2; i++) {
// 가장 작은 지점을 지나는 경우 처리
			if (i == sx/2) {
				cx = i*2, cy = 0;
				int d=1;
				while (cx != i*2+1 || cy != C-1) {
					nx = dir[d][0] + cx, ny = dir[d][1] + cy;
					if (nx == sx && ny == sy) d = (d+3)%MAX_D;
					else {
						ans[pos++] = dir_c[d];
						d = (d+1)%MAX_D;
						cx = nx, cy = ny;
					}
				}
				if (i != R/2-1) ans[pos++] = 'D';
				ans[pos]='\0';
				printf("%s", ans);
// 가장 작은 지점을 지나기 전
			} else if (i < sx/2) {
				printf("%s",p1);
				printf("D");
				printf("%s",p0);
				printf("D");
// 지난 후
			} else {
				printf("%s",p0);
				printf("D");
				printf("%s",p1);
				if (i != R/2-1) printf("D");
			}
		}
	}
	return 0;
}