[BOJ] 2873. 롤러코스터 ✔

2873. 롤러코스터

1. 문제

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

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

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

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

2. 입력

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

3. 출력

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

4. 풀이

Python

R, C = map(int, input().split())
hp = [list(map(int, input().split())) for _ in range(R)]

# R, C 중 하나라도 홀수일 경우 모든 칸 방문 가능
if R % 2 == 1:
    print(('R' * (C - 1) + 'D' + 'L' * (C - 1) + 'D') * (R // 2) + 'R' * (C - 1))
    
elif C % 2 == 1:
    print(('D' * (R - 1) + 'R' + 'U' * (R - 1) + 'R') * (C // 2) + 'D' * (R - 1))
    
# R, C 모두 짝수일 경우
else:
    # x, y 좌표의 합이 홀수인 칸 중 행복도가 가장 낮은 칸 찾기
    lowest = 1001
    lowestPoint = [-1, -1]
    for i in range(R):
        for j in range(C):
            if (i + j) % 2 == 1 and lowest > hp[i][j]:
                lowest = hp[i][j]
                lowestPoint = [i, j]
     
    # 찾은 칸을 제외한 모든 칸을 방문
    result = ('D' * (R - 1) + 'R' + 'U' * (R - 1) + 'R') * (lowestPoint[1] // 2)
    x = 2 * (lowestPoint[1] // 2)
    y = 0
    xbound = 2 * (lowestPoint[1] // 2) + 1
    while x != xbound or y != R - 1:
        if x < xbound and [y, xbound] != lowestPoint:
            x += 1
            result += 'R'
        elif x == xbound and [y, xbound - 1] != lowestPoint:
            x -= 1
            result += 'L'
            
        if y != R - 1:
            y += 1
            result += 'D'

    result += ('R' + 'U' * (R - 1) + 'R' + 'D' * (R - 1))*((C - lowestPoint[1] - 1) // 2)
    
    print(result)

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int R, C;
    cin >> R >> C;
    
    vector<vector<int>> map(R, vector<int>(C));
    int input, lowest(1001), minX(0), minY(0);
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            cin >> input;
            map[i][j] = input;
            
            // R, C가 모두 짝수일 때를 대비해 행과 열의 합이 홀수이고 최저값을 가지는 점을 찾기
            if (lowest > input && (i + j) % 2 == 1)
            {
                minX = j;
                minY = i;
                lowest = input;
            }
        }
    }
    
    string result;
    
    // R이나 C가 홀수일 때는 ㄹ자로 모든 칸을 방문
    if (R % 2)
    {
        for (int i = 0; i < R / 2; ++i)
        {
            result += string(C - 1, 'R') + "D" + string(C - 1, 'L') + "D";
        }
        result += string(C - 1, 'R');
        cout << result;
    }
    else if (C % 2)
    {
        for (int i = 0; i < C / 2; ++i)
        {
            result += string(R - 1, 'D') + "R" + string(R - 1, 'U') + "R";
        }
        result += string(R - 1, 'D');
        cout << result;
    }
    // R, C가 모두 짝수일 때는 lowestPoint만 방문하지 않음
    else
    {    
        for (int i = 0; i < minX / 2; ++i)
        {
            result += string(R - 1, 'D') + "R" + string(R - 1, 'U') + "R";
        }
        
        int xBound = (minX / 2) * 2 + 1;
        int x = (minX / 2) * 2;
        int y = 0;
        while (x != xBound || y != R - 1)
        {
            if (x < xBound && (x + 1 != minX || y != minY))
            {
                ++x;
                result += "R";
            }
            else if (x == xBound && (x - 1 != minX || y != minY))
            {
                --x;
                result += "L";
            }
            
            if (y != R - 1)
            {
                ++y;
                result += "D";
            }
        }
        
        for (int i = xBound + 1; i < C; i += 2)
        {
            result += "R" + string(R - 1, 'U') + "R" + string(R - 1, 'D');
        }
        
        cout << result;
    }
    
    return 0;
}