[BOJ 2873] 롤러코스터

Link

http://icpc.me/2873

Problem

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

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

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

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

Solution

일단 가로와 세로 중 하나라도 홀수이면 모든 지점을 거쳐서 끝점으로 갈 수 있다.

만약 가로가 홀수이면 세로 끝 -> 오른쪽 -> 세로 처음 -> 오른쪽 -> .... -> 세로 끝으로 하는 방식으로 하면 된다.

이제 둘다 짝수일 때가 문제인데, 두 개의 index의 기우성이 같은 점을 "1", 다른 점을 "0"이라고 칭하면

반드시 한번 움직일 때마다 1에서 0 혹은 0에서 1로 가는 수 밖에 없고, 최대가 되기 위해서는 기쁨 점수가 가장 낮은 블럭 N개를 제외하고 모두 방문하는 것이 유리함을 알 수 있다.

짝수인 경우 2*2 직사각형들로 전부 분해할 수 있고, 모든 점을 방문하면 반드시 1 -> 0 -> 1 -> 0의 4개의 경로 패턴이 반복되고, 우리가 원하는 시작과 끝은 둘 다 1이므로 모두 방문하는 것은 불가능함을 알 수 있다. (N=0은 불가)

위에서 말했다시피 시작과 끝이 둘다 1이므로 반드시 4개의 패턴이 아니라 3개의 패턴만이 반복되는, 즉 시작이 1에서 0으로 바뀌는 지점이 존재해야 함을 알 수 있다.

또한, 0점이 가장 작은 값을 가지면 그 줄에서는 지그재그로, 나머지 줄에서는 원래 가던대로 가면 항상 방문이 가능함을 알 수 있다. (N=1)

마지막으로 1점이 가장 작은 값을 가지면 반드시 지나가지 못하는 0점이 추가로 최소 하나 더 생기게 된다.

• 우리의 출발점은 반드시 1에서 시작해서 1로 끝나야 한다.
• 반드시 1에서 시작하면 다음은 0, 0으로 시작하면 1이므로 같은 블록 내의 0을 방문하기 위해서는 그 사이에 1이 최소 하나는 존재해야 한다.
• 다른 말로, 0 -> 0의 경로는 존재하지 않고, 반드시 1에서 출발해서 0으로 끝이 나는 3개의 경로 패턴이 존재하지 않음을 의미한다.
• 이는 모순이므로, 반드시 다른 경로에서 0점을 지나치지 않으면서 3개의 패턴이 반복되는 (1-> 0 -> 1) 부분이 생기게 된다.

하지만 이렇게 두 점을 거르고 가지 않는 것보다 위에서 추가로 생긴 0점만 안 지나고 1점을 지나는 경우가 더 효율적이다.

따라서, 1점의 경우는 고려하지 않고 0점에서의 최솟값을 뽑은 이후 그 점만 지나치지 않게 코드를 구현해주면 된다.

Code

#include <bits/stdc++.h>
using namespace std;
int mn = 1005, mi, mj;
int mp[1005][1005];
 
int main() {
    int r, c;
    scanf("%d %d", &r, &c);
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) {
        scanf("%d",&mp[i][j]);
        if((i+j)%2 && mn > mp[i][j]) mn = mp[i][j], mi = i, mj = j;
    }
    if(r%2) {
        for(int i=0;i<r/2;i++) {
            for(int j=1;j<c;j++) printf("R");
            printf("D");
            for(int j=1;j<c;j++) printf("L");
            printf("D");
        }
        for(int j=1;j<c;j++) printf("R");
    }    
    else {
        if(c%2) {
            for(int i=0;i<c/2;i++) {
                for(int j=1;j<r;j++) printf("D");
                printf("R");
                for(int j=1;j<r;j++) printf("U");
                printf("R");
            }
            for(int i=1;i<r;i++) printf("D");
        }
        else {
            for(int i=0;i<r/2;i++) {
                if(i < mi/2) {
                    for(int j=1;j<c;j++) printf("R");
                    printf("D");
                    for(int j=1;j<c;j++) printf("L");
                }
                else if (i==mi/2) {
                    for(int j=0; j<c/2;j++) {
                        if(j< mj/2) {
                            printf("DRU");
                        }
                        else if (j==mj/2) {
                            if(mi%2) printf("RD");
                            else printf("DR");
                        }
                        else {
                            printf("URD");
                        }
                        if(j+1 != c/2) printf("R");
                    }
                }
                else {
                    for(int j=1;j<c;j++) printf("L");
                    printf("D");
                    for(int j=1;j<c;j++) printf("R");
                }
                if(i+1 != r/2) printf("D");
            }
        }
    }
    return 0;
}