[C++] BAEKJOON 2873 롤러코스터

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

2873번: 롤러코스터

그리디 알고리즘 을 사용하여 문제를 해결하였습니다.

가로와 세로의 길이에 따라서 갈 수 있는 경로가 다릅니다. 가로와 세로의 길이 중 홀수가 하나라도 있다면 모든 경로를 순회할 수 있습니다. 이제 문제는 짝수, 짝수인 경우입니다.

가로와 세로의 길이가 둘 다 짝수인 경우에는 지나지 못하는 지점이 생기게 됩니다. 왜 그럴까요?

위 그림을 보면 흰색 -> 검은색 -> 흰색 -> … -> 검은색 -> 흰색 으로 경로가 생기는 걸 알 수 있습니다. 다음과 같은 직사각형 격자에서는 흰색과 검은색의 수가 같기 때문에 흰색에서 시작해서 흰색으로 끝날 경우 검은색을 하나 지나지 못하게 됩니다. 따라서 가장 작은 검은색 지점을 찾고, 그 지점을 제외한 나머지 경로를 찾아주도록 합니다.

경로를 찾기 위해서는 출발지점과 끝지점에서 동시에 출발하여 만날 경우 두 경로를 합쳐줍니다. 이를 위해 크게 2가지 과정을 거칩니다.

1. 출발지점에서 출발한 경로는 행 기준으로 최소지점 한 칸 윗 행까지 모든 점을 지나오고 도착지점에서 출발한 경로는 행 기준으로 최소지점과 같은 행까지 오도록 합니다.
2. 열 기준으로 좁혀가며 만나는 지점을 찾도록 합니다.

#include <iostream>
#include <algorithm>

using namespace std;

int board[1000][1000];

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

int main(int argc, const char * argv[]) {
    
    int row,col;
    cin >> row >> col;
    
    for (int i=0;i<row;i++){
        for (int j=0;j<col;j++){
            cin >> board[i][j];
        }
    }
    string answer = "";
    
    // row 가 홀수인 경우
    if (row%2==1){
        // 0: 오른쪽, 1: 왼쪽
        int dir = 1;
        for (int i=0;i<row;i++){
            dir = 1-dir;
            for (int j=0;j<col-1;j++){
                if (dir) answer+="L";
                else answer+="R";
            }
            if (i!=row-1) answer+="D";
        }
    }
    // col 이 홀수인 경우
    else if (col%2 == 1) {
        // 0: 아래쪽, 1:위쪽
        int dir = 1;
        for (int i=0; i<col; i++) {
            dir = 1-dir;
            for (int j=0;j<row-1;j++){
                if (dir) answer+="U";
                else answer+="D";
            }
            if (i!=col-1) answer+="R";
        }
    }

    // row, col 이 둘 다 짝수인 경우
    else {
        // 지나지 말아야 할 점 찾기
        int x,y;
        x=0;
        y=1;
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if ((i+j)%2==1 && board[x][y] > board[i][j]){
                    x = i;
                    y = j;
                }
            }
        }
        
        int x1=0;
        int y1=0;
        int x2=row-1;
        int y2=col-1;
        string subAnswer = "";
        while (x2-x1>1){
            if (x1/2 < x/2) {
                append(answer, 'R', col-1);
                append(answer, 'D', 1);
                append(answer, 'L', col-1);
                append(answer, 'D', 1);
                x1 += 2;
            }
            if (x/2 < x2/2) {
                append(subAnswer, 'R', col-1);
                append(subAnswer, 'D', 1);
                append(subAnswer, 'L', col-1);
                append(subAnswer, 'D', 1);
                x2 -= 2;
            }
        }
        while (y2-y1>1){
            if (y1/2 < y/2) {
                append(answer, 'D', 1);
                append(answer, 'R', 1);
                append(answer, 'U', 1);
                append(answer, 'R', 1);
                y1 += 2;
            }
            if (y/2 < y2/2) {
                append(subAnswer, 'D', 1);
                append(subAnswer, 'R', 1);
                append(subAnswer, 'U', 1);
                append(subAnswer, 'R', 1);
                y2 -= 2;
            }
        }
        if (y == y1) {
            append(answer, 'R', 1);
            append(answer, 'D', 1);
        } else {
            append(answer, 'D', 1);
            append(answer, 'R', 1);
        }
        reverse(subAnswer.begin(), subAnswer.end());
        answer += subAnswer;
    }
    
    
    
    
    cout << answer << "\n";
    
    return 0;
}