[백준] 2873 - 롤러코스터

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

2873번: 롤러코스터

 

그리디 알고리즘 카테고리에 있지만 구현의 성격이 짙은 문제였다.

 

문제의 핵심은 다음과 같다.

1행부터 R행, 1열부터 C열까지 있다고 보았을 때,

1. 행 또는 열이 홀수인 경우 모든 칸을 지날 수 있다.
2. 행과 열이 모두 짝수인 경우는 다음과 같다.
   •  행 + 열이 홀수가 나오는 칸의 최솟값을 지나지 않아야 한다. 그 이유는 다음과 같다.
   • R행 C열 짜리의 체스판이라고 생각했을 때, 체스판은 현재 칸의 인접한 4칸은 모두 다른 색이다. 따라서 현재 칸에서 이동하려면 무조건 다른 칸으로 이동하여야 한다.
   • 1행 1열을 흰색 칸이라고 보았을 때, R행 C열 칸도 흰색이다. 따라서 최소 1칸은 지나가지 못한다.
     • 흰색 칸을 방문하지 않았다고 했을 때, 도착점까지 모든 칸을 방문할 수 없다.
     • 검은색 칸을 방문하지 않았다고 했을 때, 도착점까지 모든 칸을 방문할 수 있다.

이 부분만 캐치하였다면 다음은 구현의 문제이다. 1번의 경우 간단하니 넘어가고, 2번의 경우를 살펴보자.

1. 최솟값(지나지 않을 칸)을 가진 칸에 대해서 좌측 상단으로 이동한다. 이때, 행의 번호가 최솟값을 가진 칸의 행 번호보다 작은 짝수일 때 멈춘다.
   
   • 만약 최솟값을 가진 칸이 3행일 경우, 2행 1열에서 멈춘다.
   • 만약 최솟값을 가진 칸이 6행일 경우, 4행 1열에서 멈춘다.
2. DR - RU 연산을 반복하며 다음 짝수 행까지 이동한다.
3. 이후 도착칸까지 이동한다.

이 부분은 코드로 보는 것이 이해가 더 잘될 듯싶다.

 

#include <iostream>
using namespace std;

int map[1001][1001];
int minElement = -1, mini = -1, minj = -1;
string ans = "";
int n, m;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> map[i][j];
		}
	}
	if (n % 2 != 0 || m % 2 != 0) {
		if (n % 2 != 0) { //세로가 홀수
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m - 1; j++) {
					if (i % 2 == 0) {
						cout << 'R';
					}
					else cout << 'L';
				}
				if (i < n - 1) cout << 'D';
			}
		}
		else if (m % 2 != 0) { //가로가 홀수
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n - 1; j++) {
					if (i % 2 == 0) {
						cout << 'D';
					}
					else cout << 'U';
				}
				if (i < m - 1) cout << 'R';
			}
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if ((i + j) % 2 != 0) {
					if (minElement == -1 || minElement > map[i][j]) {
						minElement = map[i][j];
						mini = i; minj = j;
					}
				}
			}
		}
		for (int i = 0; i < (mini % 2 == 0 ? mini - 2 : mini - 1); i++) {
			for (int j = 0; j < m - 1; j++) {
				if (i % 2 == 0)ans += "R";
				else ans += "L";
			}
			ans += "D";
		}
		for (int i = 0; i < minj - 1; i++) {
			if (i % 2 == 0)ans += "DR";
			else ans += "UR";
		}
		for (int i = minj; i < m; i++) {
			if (i % 2 == 0)ans += "RU";
			else ans += "RD";
		}
		if (mini % 2 != 0) {
			n -= mini + 1;
		}
		else {
			n -= mini;
		}
		for (int i = 1; i <= n; i++) {
			ans += "D";
			for (int j = 1; j < m; j++) {
				if (i % 2 != 0)ans += "L";
				else ans += "R";
			}
		}
		cout << ans;
	}
}