[백준] 2873번 롤러코스터

롤러코스터(https://www.acmicpc.net/problem/2873)

---

1. 이해하기

• 가장 큰 기쁨을 주는 롤러코스터의 움직임을 출력하는 문제.

• 행 혹은 열이 홀수인 경우, 모든 지역 탐색이 가능하다.

• 행, 열이 모두 짝수인 경우에는 어느 한 지역을 가지 않아야 한다.

  • 가지 않는 한 지역을 구하는 기준은 다음과 같다.
    • (행+열)이 홀수인 지역 중 가장 행복 지수가 낮은 지역을 구한다.
    • 이유는 (행+열)이 짝수인 지역을 가지 않을 경우 한 곳은 두번 이상을 거쳐야 가장 오른쪽 아래 칸에 도착을 할 수 있기 때문이다.

• 가지 않는 지역을 결정했으면 그 지역을 기준으로 출발지역과 끝지역에서 서로 만나는 코스를 만든다고 생각한다.

  1. 가지 않는 지역을 기준으로 출발지역에서는 아래로 2칸, 끝지역에서는 위로 2칸을 갈 수 있는지 본다. 그리고 출발지역과 끝지역의 행 차이가 1인 지역에서 멈춘다.

     

  2. 그 다음에는 가지 않는 지역을 기준으로 옆으로 옆으로 2칸을 갈 수 있는지 본다. 마찬가지로 출발지역과 끝지역의 열 차이가 1인 지역에서 멈춘다.

     

  3. 마지막에는 위쪽으로 갈 수 있는지, 아래쪽으로 갈 수 있는지를 체크해서 방향을 넣어준다.

---

2. 구현하기

#include <iostream>
#include <algorithm>
using namespace std;

int happy[1000][1000];

void append(string& ans, char c, int end) {
    for(int i = 0; i < end; i++) {
        ans += c;
    }
}

int main() {
    int R,C;
    cin >> R >> C;
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            cin >> happy[i][j];

    if(R%2==1) {
        string ans = "";
        bool r = true;
        for(int i = 0; i < R; i++) {
            if(r) {
                append(ans,'R',C-1);
                r = !r;
            } else {
                append(ans,'L',C-1);
                r = !r;
            }
            if(i+1 < R) ans += 'D';
        }
        cout << ans << '\n';
    } else if(C%2 == 1) {
        string ans = "";
        bool d = true;
        for(int i = 0; i < C; i++) {
            if(d) {
                append(ans,'D',R-1);
                d = !d;
            } else {
                append(ans,'U',R-1);
                d = !d;
            }
            if(i+1 < C) ans += 'R';
        }
        cout << ans << '\n';
    } else {
        int x = 0,y = 1;
        int minVal = happy[0][1];
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if((i+j)%2 == 1 and minVal > happy[i][j]) {
                    minVal = happy[i][j];
                    x = i; y = j;
                }
            }
        }
        string ans = "", revAns = "";
        int sr = 0, sc = 0, er = R-1, ec = C-1;
        while(er - sr > 1) {
            if(sr+1 < x) {
                append(ans,'R',C-1);
                append(ans,'D',1);
                append(ans,'L',C-1);
                append(ans,'D',1);
                sr+=2;
            }
            if(er-1 > x) {
                append(revAns,'R',C-1);
                append(revAns,'D',1);
                append(revAns,'L',C-1);
                append(revAns,'D',1);
                er -= 2;
            }
        }
        while(ec - sc > 1) {
            if(sc+1 < y) {
                append(ans,'D',1);
                append(ans,'R',1);
                append(ans,'U',1);
                append(ans,'R',1);
                sc += 2;
            }
            if(ec-1 > y) {
                append(revAns,'D',1);
                append(revAns,'R',1);
                append(revAns,'U',1);
                append(revAns,'R',1);
                ec -= 2;
            }
        }
        if(x == sr+1) {
            append(ans,'R',1);
            append(ans,'D',1);
        } else if(x == er-1) {
            append(ans,'D',1);
            append(ans,'R',1);
        }
        reverse(revAns.begin(),revAns.end());
        ans += revAns;
        cout << ans << '\n';
    }
    return 0;
}