문제를 보자마자 row와 col이 홀수와 짝수일 경우를 나눠야 겠다는 생각이 들었다.
그러면 아래 처럼 세 가지 경우가 발생한다. 시작 지점은 (1, 1)이라 가정하자.
row가 홀수인 경우
‘ㄹ’자로 내려오면 된다.
현재 행의 번호가 홀수이면 오른쪽으로, 짝수이면 왼쪽으로 이동하면 되며 각 행에서 마지막 열일 때 아래로 한 칸 이동한다. (도착지점일 때는 아래로 이동하지 않음)
row가 짝수이고 col이 홀수인 경우
‘ㄹ’을 오른쪽으로 90도 회전한 모양으로 내려오면 된다.
현재 열의 번호가 홀수이면 아래로, 짝수이면 위로 이동하면 되며 각 열에서 마지막 행일 때 오른쪽으로 한 칸 이동한다. (도착지점일 때는 오른쪽으로 이동하지 않음)
row와 col 모두 짝수인 경우
row와 col이 모두 짝수일 때는 모든 칸을 다 방문할 수 없다.
행과 열 모두 짝수이므로 체스판을 떠올려보자. 시작 지점을 흰색으로 칠하면 도착 지점도 흰색 칸이다.
그리고 조금만 생각해보면, 검은 칸을 한 칸 지나지 않으면 체스판 위의 다른 모든 칸을 방문할 수 있지만 흰 칸을 하나라도 방문하지 않으면 도착 지점에 도달할 수 없다는 것을 알 수 있다.
그래서 우선 방문하지 않을 칸을 하나 정한다. 반복문을 돌며 가장 작은 값을 가지는 검은 칸(행+열의 값이 홀수인 칸)을 찾는다.
그럼 이제 문제를 변형해보자. 원래의 문제는 혼자서 (1, 1)에서 (R, C)까지 이동하는 문제이지만, (1, 1)와 (R, C)에 있는 두 사람이 서로 만날 때 까지 이동하는 문제와 같다. (1, 1)에 있는 사람을 A, (R, C)에 있는 사람을 B라 하자. 우리는 A와 B가 이동하는 경로를 구한 뒤, A의 경로에다가 B의 경로를 거꾸로 뒤집은 것을 더하면 원래 문제의 정답을 구할 수 있다.
먼저 행부터 이동한다. 만약 현재의 행 번호와 선택된 검은 칸의 행 차이가 2 이상이면 ‘ㄷ’을 좌우대칭한 것처럼 다녀올 수 있다. B와 A가 있는 행의 차이가 1보다 작거나 같아질 때까지 이 과정을 반복한다.
그러면 A와 B는 이웃한 행에 있을 것이고, 그 두 행 중에 선택된 검은 칸이 있으므로 더 이상 위에서처럼 칸들을 방문할 수 없다. 이제부터는 열을 행과 같은 식으로 처리한다. A와 B의 열 차이가 1 이하가 될 때 까지 U-R-D-R로 이동한다.
이 과정을 거치면 2X2 크기의 칸만 남게 되는데, 검은 칸의 위치에 따라 A가 R-D 또는 D-R의 경로로 이동하면 된다.
A의 경로에다가 B의 경로를 뒤집은 것을 더하면 최종 정답을 얻는다.
#include <iostream>
#include <string>
#include <algorithm>
#define MAX 1001
using namespace std;
int weight[MAX][MAX];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int R, C, i, j;
string answer = "";
cin >> R >> C;
for (i = 1; i <= R; i++) {
for (j = 1; j <= C; j++) cin >> weight[i][j];
}
if (R % 2) { // 'Z'자 모양으로 내려옴
for (i = 1; i <= R; i++) {
for (j = 1; j <= C - 1; j++) answer += (i % 2) ? "R" : "L";
if (i < R) answer += "D";
}
}
else if (C % 2) { // (R, C): (짝수, 홀수)
for (i = 1; i <= C; i++) {
for (j = 1; j <= R - 1; j++) answer += (i % 2) ? "D" : "U";
if (i < C) answer += "R";
}
}
else { // (R, C): (짝수, 짝수)
// 검은 칸 중 최솟값 구하기
int minBlack = MAX, blackR, blackC;
int now1R = 1, now1C = 1, now2R = R, now2C = C; // now1: start2black 구성, now2: black2dst 구성
string start2black = "", black2dst = "";
for (i = 1; i <= R; i++) {
for (j = 1; j <= C; j++) {
if ((i + j) % 2 && weight[i][j] < minBlack) {
minBlack = weight[i][j];
blackR = i;
blackC = j;
}
}
}
// 두 행씩 묶어서 이동
while (now2R - now1R > 1) {
if ((now1R - 1) / 2 < (blackR - 1) / 2) {
for (i = 1; i <= C - 1; i++) start2black += (now1R % 2) ? "R" : "L";
start2black += "D";
now1R++;
}
if ((now2R - 1) / 2 > (blackR - 1) / 2) {
for (i = 1; i <= C - 1; i++) black2dst += (now2R % 2) ? "L" : "R";
black2dst += "D";
now2R--;
}
}
// 두 열씩 묶어서 이동
while (now2C - now1C > 1) {
if ((now1C - 1) / 2 < (blackC - 1) / 2) {
start2black += "DRUR";
now1C += 2;
}
if ((now2C - 1) / 2 > (blackC - 1) / 2) {
black2dst += "DRUR";
now2C -= 2;
}
}
if (blackC == now1C) start2black += "RD";
else start2black += "DR";
answer += start2black;
reverse(black2dst.begin(), black2dst.end());
answer += black2dst;
}
cout << answer << endl;
return 0;
}