[백준/BOJ] 2873 롤러코스터

문제 : 2873 롤러코스터

2873번: 롤러코스터

롤러코스터가 갈 수 있는 칸이 주어지고 이를 지나면서

가장 최대의 행복값을 가지도록 경로를 구현하는 문제이다.

기본적으로 홀*홀, 짝*홀, 홀*짝 경우에서는 ㄹ자로 순회하면 모든 칸을 지날 수 있으므로

행이나 열이 홀수인 방향을 찾아 모든 칸을 지나도록 경로를 만들어 출력하면 된다.

 

결국 이문제의 문제는 짝*짝 상황에서 어떻게 최댓값을 찾아내냐는 것인데

어찌어찌 머리를 굴리다 보면 [짝, 홀] 칸이나 [홀, 짝] 칸 하나만 지나지 않고

다른 모든칸을 지날 수 있는 것을 알 수 있다.

짝수 줄을 2줄씩 끊어 순회한다고 생각하면 결국 ㄷ자로 움직여서

왼쪽 위에서 왼쪽 아래로 오게 되는 것인데이를 오른쪽 아래로 보내기 위해서는

한 번만 반대방향으로 가면 되는 것을 알 수 있고 이를 이용하면 2*n칸에서

움직일 때 한 칸을 제외한 모든 칸을 순회하면서 반대방향으로 갈 수 있다는 사실을 알아낼 수 있다.

 

그렇기 때문에 먼저 [짝, 홀], [홀, 짝] 칸의 최솟값을 알아내고

그 칸이 포함된 2줄을 제외한 나머지 가로줄은 다 ㄷ자로 순회하고

그 줄만 그 칸을 건너뛰어서 넘어가는 경로를 만들어 출력해주면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, x, y, mn=1e9+7;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++){
            ll a;
            cin >> a;
            if ((i+j)%2 && a<mn){
                mn=a;
                x=i, y=j;
            }
        }
    }
    if (N%2){
        for (int i=0;i<N;i++){
            for (int j=0;j<M-1;j++){
                if (i%2)
                    cout << "L";
                else
                    cout << "R";
            }
            if (i!=N-1)
                cout << "D";
        }
    }
    else if (M%2){
        for (int i=0;i<M;i++){
            for (int j=0;j<N-1;j++){
                if (i%2)
                    cout << "U";
                else
                    cout << "D";
            }
            if (i!=M-1)
                cout << "R";
        }
    }
    else{
        for (int i=0;i<(x/2)*2;i++){
            for (int j=0;j<M-1;j++){
                if (i%2)
                    cout << "L";
                else
                    cout << "R";
            }
            cout << "D";
        }
        ll dx=(x/2)*2, dy=0;
        while (1){
            if (dx==(x/2)*2+1 && dy==M-1)
                break;
            if (dx==(x/2)*2 && (dx+1!=x || dy!=y)){
                cout << "D";
                dx++;
            }
            if (dy<M-1 && (dx!=x || dy!=y)){
                cout << "R";
                dy++;
            }
            if (dx==(x/2)*2+1 && dy==M-1)
                break;
            if (dx==(x/2)*2+1 && (dx-1!=x || dy!=y)){
                cout << "U";
                dx--;
                if (dy<M-1 && (dx!=x || dy!=y)){
                    cout << "R";
                    dy++;
                }
            }
        }
        for (int i=(x/2+1)*2;i<N;i++){
            cout << "D";
            for (int j=0;j<M-1;j++){
                if (i%2)
                    cout << "R";
                else
                    cout << "L";
            }
        }
    }
    return 0;
}