[백준 C++] 2873 롤러코스터

문제

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.

출력

첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.

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

풀이

최백준님의 풀이를 참고했습니다. (> https://www.slideshare.net/Baekjoon/baekjoon-online-judge-2873)

맵크기 RxC에따라 총 2가지로 롤러코스터 형태가 나뉘어진다.

1. R, C중 하나이상이 홀수인경우
   
   롤러코스터는 최대한 많은 칸을 지나갈수록 이득이므로,
   R과 C중 하나라도 홀수라면 지그재그 형식으로 만들 수 있다.
   이때의 코드는 아래처럼 구할 수 있다.
   
   
   
2. R, C가모두 짝수인경우
   이때는 어떠한 경로를 그린다해도 결국에 못지나가는 한 점이 있다는 것을
   그리다보면 알 수 있다.
   그림처럼 별표시한곳을 뺀 모든 칸을 지나가는 경로가 그려진다.
   이때 별표시 칸의 규칙이있는데 그것이 x%2 != y%2이다.
   즉 x,y가 홀짝또는 짝홀인 좌표인것.
   그럼 여러개의 별표시 좌표가 있을것인데 문제에서 원하는 결과는 지나가는 모든경로의 숫자합이 최대가 되야하므로,
   위에서 구한 좌표들중 그 칸에 쓰인 숫자가 가장 작은점이 별의 위치가 된다.
   
   
   그럼 이제 별표시칸을 제외한 경로를 그리는 방법 찾아보자.
   총 3가지 단계로 나뉜다.
   
   이제 1단계를 보자.
   이렇게 경로를 짜면 항상 끝은 좌측하단으로 끝낼수있다.
   
   
   다음으로 2단계이다.
   
   DRUD 순으로 x,y좌표를 탐색하다가 만약 별표시 좌표를 만나면
   방향을 바꾸지않고 그상태에서 y좌표를 +1 하여 우측으로 이동한뒤에(당연히 R 출력) 그리고 원래 가던 D또는 U방향을 그대로 유지하며
   DRUD순으로 진행하면된다.
   이때 총 진행횟수는 별표시를 제외한 7칸 - 1 회이므로,
   2*(C - 1) 회이다.
   
   
   마지막 3단계는 아래와 같다.
   2단계에서 우측아래에서 좌표가 끝났으므로 이번탐색은
   위의 1단계와 같지만 방향은 반대로 진행하면된다.

아마 이런부류의 구현문제는 처음부터끝까지 브루트포스알고리즘이라면,
그안에서 반복횟수를 줄이기위한 규칙을 찾기위해
때로는 이렇게 단계를 나눠서 코드를 짜봐야 할 것같다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc(x) x.c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define P() pop()
#define B() back()
#define F() front()
#define len(x) x.length()
#define sz(x) ((int)x.size())
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) (x).begin(),(x).end() //sort등에서 컨테이너 전체를 처리해야할때 사용
#define ct continue
#define br break
#define rt return
#define MAX 1001
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
using std::vector; using std::stack; using std::queue; using std::tuple; using std::set; using std::list; using std::bitset; using std::string; using std::pair; using std::greater;
using std::tie; using std::sort; using std::max_element; using std::min_element; using std::fill;
//using std::max; //using std::min; //using std::map;
typedef long long ll; typedef unsigned long long ull;
typedef pair<int, int> pii; typedef pair<double, int> pdi; typedef pair<int, double> pid; typedef pair<double, double> pdd; typedef pair<int, ll> pil;
typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef pair<ull, ull> pullull; typedef pair<int, char> pic; typedef pair<char, int> pci;
typedef pair<char, char> pcc; typedef pair<long, char> plc; typedef pair<char, long> pcl; typedef pair<ll, char> pllc; typedef pair<char, ll> pcll;
typedef pair<ull, char> pullc; typedef pair<char, ull> pcull; typedef pair<int, string> pis; typedef pair<string, int> psi; typedef pair<long, string> pls;
typedef pair<string, long> psl; typedef pair<ll, string> plls; typedef pair<string, ll> psll; typedef pair<ull, string> pulls;
typedef pair<string, ull> psull; typedef pair<string, string> pss;
typedef tuple<int, int, int> tiii; typedef tuple<int, int, int, int> tiiii;
typedef tuple<ll, ll, ll> tlll; typedef tuple<ll, ll, ll, ll> tllll;
typedef vector<string> vs; typedef queue<string> qs; typedef stack<string> ss; typedef dq<string> dqs; typedef pq<string> pqs;
typedef vector<char> vc; typedef queue<char> qc; typedef stack<char> sc; typedef dq<char> dqc; typedef pq<char> pqc;
typedef vector<int> vi; typedef queue<int> qi; typedef stack<int> si; typedef dq<int> dqi; typedef pq<int> pqi;
typedef vector<pii> vii; typedef queue<pii> qii; typedef stack<pii> sii; typedef dq<pii> dqii; typedef pq<pii> pqii;
typedef vector<tiii> viii; typedef queue<tiii> qiii; typedef stack<tiii> siii; typedef dq<tiii> dqiii; typedef pq<tiii> pqiii;
typedef vector<tiiii> viiii; typedef queue<tiiii> qiiii; typedef stack<tiiii> siiii; typedef dq<tiiii> dqiiii; typedef pq<tiiii> pqiiii;
typedef vector<pll> vll; typedef queue<pll> qll; typedef stack<ll> sll; typedef dq<pll> dqll; typedef pq<pll> pqll;
typedef vector<tlll> vlll; typedef queue<tlll> qlll; typedef stack<tlll> slll; typedef dq<tlll> dqlll; typedef pq<tlll> pqlll;
typedef vector<tllll> vllll; typedef queue<tllll> qllll; typedef stack<tllll> sllll; typedef dq<tllll> dqllll; typedef pq<tllll> pqllll;
template <class T> inline T sq(T num) { rt num* num; }//제곱함수
template <class T> inline T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
template <class T> inline T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
template <class T> inline void msq(T a) { while (!a.empty()) a.pop(); }//queue clear
template <class T> inline void msv(T a) { a.clear(); }//vector clear
template <class T> inline void msdq(T a) { a.clear(); }//deque clear
template <class T> inline void msm(T a) { a.clear(); }//map clear
template <class T> inline void mss(T a) { while (!a.empty()) a.pop(); }//stack, set clear
template <class T> inline void mspq(T a) { while (!a.empty()) a.pop(); }//priority_queue clear
//pii operator - (pii a, pii b) { return pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { return a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { return a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; return a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; return a >= b; }

int R, C;
int map[MAX][MAX];
bool visited[MAX][MAX];
int dxy[][2] = { {1,0}, {0, 1}, {-1, 0}, {0, -1} };


void init();
void func();

void init() {
    scanf("%d%d", &R, &C);
    rep(i, R)
        rep(j, C)
            scanf("%d", &map[i][j]);
}

void func() {
    if (R % 2) { //세로줄이 홀수일때
        //모든칸을 지나면된다.
        rep(x, R) {
            rep(y, C - 1) {
                if (x % 2)
                    //홀수일떈 왼쪽
                    pr("L");
                else
                    //짝수일땐 오른쪽
                    pr("R");
            }
            if(x != R - 1)
                pr("D");
        }
    }
    else if (C % 2) { //가로줄이 홀수일때
        rep(y, C) {
            rep(x, R - 1) {
                if (y % 2)
                    pr("U");
                else
                    pr("D");
            }
            if (y != C - 1)
                pr("R");
        }
    }
    else { //세로줄이 짝수일때
        //-. 못지나가는 하나의 칸을 찾는다.
        pii blank; //칸의 좌표
        int min = 1000; //칸의 최댓값
        rep(i, R) {
            rep(j, C) {
                if (i % 2 != j % 2) {
                    if (min > map[i][j]) {
                        min = map[i][j];
                        blank = { i, j }; //좌표기록
                    }
                }
            }
        }
        int blank_X, blank_Y;
        tie(blank_X, blank_Y) = mt(blank.first, blank.second);

        //pr(">>>>>>>>>>>%d,%d\n", blank_X, blank_Y); //DEBUG

        //1단계 : 
        //pr("\n1 ====================\n"); //DEBUG
        rep(x, (blank_X/2)*2 ) { //
            rep(y, C - 1) {
                if (x % 2)
                    pr("L");
                else
                    pr("R");
            }
            pr("D");
        }
        //pr("\n2 ====================\n"); //DEBUG
        //2단계 : 구한 칸을포함하는 짝,홀의 2행
        //D R U R  반복
        int X = (blank_X / 2) * 2, Y = 0;
        int end_X = (blank_X / 2) * 2, end_Y = C - 1;
        int dxy[][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, 1} };
        char dchar[] = { 'D', 'R', 'U', 'R'};
        int dir = 0;
        int cnt = 2*(C - 1); //총 이동횟수
        while (cnt--) {
            X += dxy[dir][0];
            Y += dxy[dir][1];
            //못지나가는 칸을 만날때
            if (X == blank_X && Y == blank_Y) {
                //우측으로 한칸이동
                pr("R"); 
                Y++;
                //dir이 일정하므로 방향유지하고 계속 이동
            }
            else {
                pr("%c", dchar[dir]);
                
                dir++;
            }

            dir %= 4;
            //우측아래에 도달하면 종료
            if (X == end_X && Y == end_Y)
                break;
        }
        //pr("\n3 ====================\n"); //DEBUG
        //3단계 : 남은 행
        //      <-------
        //     ↓
        //      ------->
        cnt = R - ((blank_X / 2) + 1) * 2;
        rep(x, cnt) {
            pr("D");
            rep(_, C - 1) {
                if (x % 2)
                    pr("R");
                else
                    pr("L");
            }
        }
    }
}

int main(void) {
    init();
    func();

    rt 0;
}