[백준 2873번] [그리디 / 구현] 롤러코스터

상황 자체는 쉽게 잡았으나, 구현에서 살짝 애를 먹었다. (사실 2시간 잔 상태로 기본 틀을 잡아서 몇번 더 틀렸다 ㅋㅋ)

 

일단 이 문제를 풀기 위해서 상황 자체를 바꿔가면서 상황을 이해하려 해야한다.

 

그러면 크게 3가지 상황으로 이 문제를 바라볼 수 있다.

 

1. 세로가 홀수인 경우

이 경우는 생각보다 매우 쉽다. ㄹ모양으로 계속해서 왼쪽, 오른쪽으로 타고 내려가면 된다.

구현 자체는 zero base로 짯다고 가정했을 때, 세로가 짝수이면 Right, 홀수이면 Left를 출력해주면 된다.

 

2. 세로가 짝수이나, 가로가 홀수인 경우

이 경우는 1번 케이스의 변형으로 사각형을 90도 돌렸다고 생각해보면 1번 케이스로 치환할 수 있다.

모양은 위 아래를 반복하면서 전체적으로 오른쪽으로 진행해주면 된다.

구현 자체는 zero base로 짰다고 가정했을 때, 가로가 짝수이면 Down, 홀수면 Up을 출력해주면 된다.

 

3. 가로와 세로 모두 짝수인 경우

이 경우가 제일 문제이다.

 

행복도가 양수이므로, 최대한 많은 영역을 지나가면서 끝나는 지점으로 가는 케이스를 조사해보면 1개만 지우고 전부 다 방문할 수 있는 방법이 존재함을 파악할 수 있다.

다만, zero base로 짰다고 가정했을 때, 가로와 세로의 좌표값의 합이 홀수인 경우에만 지울 수 있다.

사실 x, y 좌표를 더해서 대각 성분을 일반화 시키는 아이디어는 N-Queen문제에서 학습하였다.(viyoung.tistory.com/128?category=884242)

 

그러면, 지울 수 있는 값 중에 최소값을 찾고 해당 지점만 제외하고 모든 지점을 방문처리해주면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define INF 987654321;

using namespace std;
int R, C;

int main(void){
    fastio;
    cin >> R >> C;
    int map[1001][1001];

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> map[i][j];
        }
    }

    // 홀수인 경우(전부 다 도는 것이 가능한 상황)
    if(R % 2 == 1){
        for(int i = 0; i < R; i++){
            if(i % 2 == 0){
                for(int j = 0; j < C - 1; j++){
                    cout << "R";
                }
                if(i != R - 1) cout << "D"; // 맨 마지막에는 내려자기 않음
            }
            else{
                for(int j = 0; j < C - 1; j++){
                    cout << "L";
                }
                if(i != R - 1) cout << "D"; // 맨 마지막에는 내려가지 않음
            }
        }
        cout << "\n";
        return 0;
    }
    else{
        if(C % 2 == 1){
            for(int i = 0; i < C; i++){
                if(i % 2 == 0){
                    for(int j = 0; j < R - 1; j++){
                        cout << "D";
                    }
                    if(i != C - 1) cout << "R"; // 맨 마지막에는 오른쪽을 가지 않음
                }
                else{
                    for(int j = 0; j < R - 1; j++){
                        cout << "U";
                    }
                    if(i != C - 1) cout << "R"; // 맨 마지막에는 오른쪽을 가지 않음
                }
            }
            cout << "\n";
            return 0;
        }
        else{
            int min_value = INF;
            int min_x;
            int min_y;
            for(int i = 0; i < R; i++){
                for(int j = 0; j < C; j++){
                    if((i + j) % 2 == 1){
                        if(min_value > map[i][j]){
                            min_value = map[i][j];
                            min_x = i;
                            min_y = j;
                        }
                    }
                }
            }

            for(int i = 0; i < (min_x / 2) * 2; i++){
                if(i % 2 == 0){
                    for(int j = 0; j < C - 1; j++){
                        cout << "R";
                    }
                    cout << "D";
                }
                else{
                    for(int j = 0; j < C - 1; j++){
                        cout << "L";
                    }
                    cout << "D";
                }
            }

            for(int j = 0; j < C; j++){
                if(min_y < j){
                    if(j % 2 == 0){
                        cout << "U";
                    }
                    else cout << "D";
                }
                else if(min_y > j){
                    if(j % 2 == 0){
                        cout << "D";
                    }
                    else cout << "U";
                }
                if(j != C - 1) cout << "R";
            }
            if((min_x / 2) * 2 + 1 != R - 1) cout << "D";

            for(int i = 0; i < R - ((min_x / 2) * 2 + 1) - 1; i++){
                for(int j = 0; j < C - 1; j++){
                    if(i % 2 == 0) cout << "L";
                    else cout << "R";
                }
                if(i != R - ((min_x / 2) * 2 + 1) - 2) cout << "D";
            }
            cout << "\n";
            return 0;
        }
    }
}