백준 2873번 롤러코스터

문제 링크 : https://www.acmicpc.net/problem/2873

2873번: 롤러코스터

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

풀이

사실 이 문제는 풀다가 가장 중요한 부분을 해결하지 못해서 백준님 코드를 보았다 ㅠㅠ

코드를 보면서 사람이 이렇게 생각할 수도 있구나.. 하고 많이 놀랐던 문제이다.

우선 이 문제를 해결하기 위해선 최대한 많은 칸을 방문하는 것이 우선이다. 모든 칸이 양수의 기쁨이므로 많이 갈수록 이득이기 때문이다.

문제를 풀 때 3가지 케이스가 있는데,

1. R(세로줄)이 홀수일 때

2. C(가로줄)이 홀수일 때

3. 둘 다 짝수일 때

 

1. 

세로줄이 홀수일 때 반드시 이런 식으로 모든 칸을 방문할 수 있다.

 

2.

가로줄이 홀수일 때는 이런식으로 모든 칸을 방문할 수 있다.

 

3. 예상했다시피 문제는 3번째 경우이다.

이 경우 반드시 "한 칸"이상 방문하지 않는 경로가 생긴다.

왜 그러냐 하면...

이런 짝수 x 짝수 행렬 모양의 체스판이 있다고 하자.

문제의 조건대로 좌측 맨 위 검은색에서 우측 맨 아래 검은색으로 가야 하는데,

모든 칸을 이동하기 위해선 짝수 x 짝수 -1번 움직인 후 검은색에 도착해야 한다.

하지만, 위 그림대로라면 검은색에서 출발하여 검은색으로 가려면 반드시 짝수번 움직여야 한다.

따라서 반드시 "한 칸"은 포기해야 한다.

 

그러면 당연히 가장 기쁨의 농도가 낮은 칸을 포기하는 게 올바른 방향이겠다.

그렇다면 가장 작은 칸을 버리고 생각해보자.

여기서 버릴 때에도 잘 생각하고 버려야 한다!!! 방금 막 버리다가 30분 동안 그린 거 다 지웠다

위에서 본 체스판에서 "한 칸"을 버릴 때 검은색~검은색으로 가는데 검은색을 버려버린다면 구석을 들어갈 수 없어서

최소 두 칸 이상(반드시 흰색 포함) 손해가 생겨버린다. 따라서 흰색(가로 + 세로 % 2 = 1) 중 가장 낮은 기쁨 칸을 버려야 한다.

 

그렇다면 버린 후 순회하는 과정을 그림으로 살펴보자.

위 그림처럼 시작과 끝부분에 사람을 두어 서로 움직여 만난다고 생각해보자.

(초록색 부분은 포기한 칸)

그림을 보면 공백이 너무 많은 것 같다. 축소시킬 순 없을까?

귀신같이 행렬이 축소되었다!!

계속해보자

짜잔! 드디어 조금 풀만해진 것 같다.

여기서 또 축소시킬 순 없을까? 당연히 할 수 있다

위에서 했던 과정을 좌-우로 적용시켜보자

이런 식으로 축소시킬 수 있다.

최종 결과는 위의 그림 또는 녹색 칠이 오른쪽 위에 있는 경우이다. 이 부분은 마지막에 처리해주면 되겠다.

코드를 보자

소스 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int happy[1001][1001];
int r, c;
string ans;
 
void append(string& ans, char c, int cnt) {
    for (int i = 0; i < cnt; i++) {
        ans += c;
    }
}
 
void side() {
    int mul = r * c - 1;
    int x = 0, y = 0;
    int dir = 0; // 0: 동 1: 북 2: 서 3: 남
    while (mul--) {
        if (dir == 0 && x + 1 < c) { // -->
            x++;
            ans.push_back('R');
        }
        else if (dir == 0 && x + 1 == c) { // 우측 끝
            y++;
            ans.push_back('D');
            dir = 3;
        }
        else if (dir == 2 && x - 1 >= 0) { // <--
            x--;
            ans.push_back('L');
        }
        else if (dir == 2 && x - 1 == -1) { // 좌측 끝
            y++;
            ans.push_back('D');
            dir = 3;
        }
        else if (dir == 3 && x + 1 == c) { //우측 경계
            x--;
            ans.push_back('L');
            dir = 2;
        }
        else if (dir == 3 && x - 1 == -1) { //좌측 경계
            x++;
            ans.push_back('R');
            dir = 0;
        }
    }
}
 

side 함수는 케이스 1을 처리한다.

void up_down() {
    int mul = r * c - 1;
    int x = 0, y = 0;
    int dir = 3; // 0: 동 1: 북 2: 서 3: 남
    while (mul--) {
        if (dir == 3 && y + 1 < r) { // up
            y++;
            ans.push_back('D');
        }
        else if (dir == 3 && y + 1 == r) { // 아래 끝
            x++;
            ans.push_back('R');
            dir = 0;
        }
        else if (dir == 1 && y - 1 >= 0) { // down
            y--;
            ans.push_back('U');
        }
        else if (dir == 1 && y - 1 == -1) { // 윗쪽 끝
            x++;
            ans.push_back('R');
            dir = 0;
        }
        else if (dir == 0 && y + 1 == r) { //아래측 경계
            y--;
            ans.push_back('U');
            dir = 1;
        }
        else if (dir == 0 && y - 1 == -1) { //위측 경계
            y++;
            ans.push_back('D');
            dir = 3;
        }
    }
}

up_down 함수는 case 2를 처리한다.

void couple() {
    int x, y;
    x = 0;
    y = 1;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if ((i + j) % 2 == 1) {
                if (happy[x][y] > happy[i][j]) {
                    x = i;
                    y = j;
                }
            }
        }
    }
    int x1 = 0;
    int y1 = 0;
    int x2 = r - 1;
    int y2 = c - 1;
    string ans2 = "";
    while (x2 - x1 > 1) {
        if (x1 / 2 < x / 2) {
            append(ans, 'R', c - 1);
            append(ans, 'D', 1);
            append(ans, 'L', c - 1);
            append(ans, 'D', 1);
            x1 += 2;
        }
        if (x / 2 < x2 / 2) {
            append(ans2, 'R', c - 1);
            append(ans2, 'D', 1);
            append(ans2, 'L', c - 1);
            append(ans2, 'D', 1);
            x2 -= 2;
        }
    }
    while (y2 - y1 > 1) {
        if (y1 / 2 < y / 2) {
            append(ans, 'D', 1);
            append(ans, 'R', 1);
            append(ans, 'U', 1);
            append(ans, 'R', 1);
            y1 += 2;
        }
        if (y / 2 < y2 / 2) {
            append(ans2, 'D', 1);
            append(ans2, 'R', 1);
            append(ans2, 'U', 1);
            append(ans2, 'R', 1);
            y2 -= 2;
        }
    }
    if (y == y1) {
        append(ans, 'R', 1);
        append(ans, 'D', 1);
    }
    else {
        append(ans, 'D', 1);
        append(ans, 'R', 1);
    }
    reverse(ans2.begin(), ans2.end());
    ans += ans2;
}

가장 중요한 couple 함수이다. 

가장 먼저, 버릴 칸을 찾고

위 설명대로 위아래 or 좌우를 자르면서 그 과정을 간단하게 문자열로 변환한다.

끝부분의 사람 좌표를 (x2, y2)로 둔 후 string ans2에 지나온 길들을 문자열로 넣고 이후에 뒤집어준다.(실제로는 하나만 움직이는 것이므로)

append 함수는 따로 만든 함수인데, 원하는 string에 원하는 문자를 원하는 수만큼 push_back 한다고 보면 된다.

int main()
{
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%d", &happy[i][j]);
        }
    }
    if (r % 2 == 1) {
        side();
        cout << ans;
    }
    else if (c % 2 == 1) {
        up_down();
        cout << ans;
    }
    else {
        couple();
        cout << ans;
    }
    return 0;
}

 main함수이다.

 

문제 번호 위에 난이도가 설명하듯 아직 내가 풀기엔 많이 어려운 문제였다.

백준님 코드와 설명을 많이 참조하긴 했지만 문제를 풀면서 많이 배울 수 있었다.

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~