[Python 알고리즘] 백준 2873번 : 롤러코스터

문제

• 상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.
• 어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.
• 이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.
• 각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

입력

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

# Case 1
3 3
5 1 3
2 4 8
1 1 2



# Case 2
2 2
2 1
3 4

출력

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

# Case 1
RRDLLDRR



#Case 2
DR

내가 제출한 풀이 - 정답

1차로 정답을 풀었긴 했는데.. 너무 더러운 코드기도 하고 봐도 좋을 게 1도 없어보여서 생략하는 게 좋을 거 같다.

깔끔한 코드로 넘어가도록 하자.

 

정답

import sys

r, c = map(int, sys.stdin.readline().split())
ground = [list(map(int, sys.stdin.readline().split())) for _ in range(r)]

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))
elif r % 2 == 0 and c % 2 == 0:
    low = 1000
    position = [-1, -1]

    for i in range(r):
        if i % 2 == 0:
            for j in range(1, c, 2):
                if low > ground[i][j]:
                    low = ground[i][j]
                    position = [i, j]
        else:  # i % 2 == 1
            for j in range(0, c, 2):
                if low > ground[i][j]:
                    low = ground[i][j]
                    position = [i, j]

    res = ('D' * (r - 1) + 'R' + 'U' * (r - 1) + 'R') * (position[1] // 2)
    x = 2 * (position[1] // 2)
    y = 0
    xbound = 2 * (position[1] // 2) + 1

    while x != xbound or y != r - 1:
        if x < xbound and [y, xbound] != position:
            x += 1
            res += 'R'
        elif x == xbound and [y, xbound - 1] != position:
            x -= 1
            res += 'L'
        if y != r - 1:
            y += 1
            res += 'D'

    res += ('R' + 'U' * (r - 1) + 'R' + 'D' * (r - 1)) * ((c - position[1] - 1) // 2)

    print(res)

문제 해석

첫 번째로 봐야할 사항은 다음과 같다.

1. 롤러코스터는 가장 왼쪽 위 칸에서 시작하며, 가장 오른쪽 아래 칸에서 도착한다.
2. 롤러코스터는 현재 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동이 가능하다.
3. 각 칸은 한 번만 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.
4. 탑승자가 얻을 수 있는 기쁨은 각 칸의 숫자를 의미한다.
5. 가장 큰 기쁨을 주는 롤러코스터를 만드는 프로그램을 작성하라.

그리디 문제인만큼 우리는 최선의 해를 찾기 위해 각 경우의 수마다 코드를 다르게 처리 해줄 것이다.

 

1. r(행)이 홀수인 경우

# 입력
5 5
5 1 3 4 7
2 4 8 1 3
1 1 2 9 7
3 1 3 8 7
5 3 3 4 9

r이 홀수인 경우에는 이러한 과정을 하게 된다면 모든 칸을 방문할 수 있게 된다.

if r % 2 == 1:
    print(('R' * (c - 1) + 'D' + 'L' * (c - 1) + 'D') * (r // 2) + 'R' * (c - 1))

그러한 코드는 이 부분이고, print가 복잡하게 들어가있어 쉽게 하나하나 설명해주겠다.

# c - 1(현재 있는 칸은 세지 않아야하기 때문에)만큼 오른쪽 이동 후 아래로 이동
'R' * (c - 1) + 'D'

# c - 1만큼 왼쪽 이동 후 아래로 이동
'L' * (c - 1) + 'D'

# 위에 있는 작업을 r(행) // 2만큼 반복
# r(행) // 2만큼 반복하는 이유는 오른쪽 이동, 왼쪽 이동을 하면 총 높이 2칸을 이동하기 때문이다.
* (r // 2)

# r // 2를 하게 되면 마지막 줄이 남기 때문에 오른쪽 이동 후 끝낸다.
# r이 홀수인 경우에는 무조건 마지막 줄은 오른쪽 이동이다.
'R' * (c - 1)

 

2. c(열)가 홀수인 경우

 

c가 홀수인 경우에는 이러한 과정을 하게 된다면 모든 칸을 방문할 수 있게 된다.

 

elif c % 2 == 1:
    print(('D' * (r - 1) + 'R' + 'U' * (r - 1) + 'R') * (c // 2) + 'D' * (r - 1))

이 부분에 대한 설명은 r이 홀수인 경우랑 구성이 같기 때문에 따로 설명하지 않겠다.

 

3. r, c가 짝수인 경우

사실상 이 부분이 해당 문제에 하이라이트라고 봐도 된다. 아마 이 부분에서 구현하기가 힘들어서 정답률이 낮은 거 같다.

 

r과 c가 모두 짝수인 경우에는 무조건 1칸을 제외하고 이동을 해야한다.

근데, 모든 칸을 제외할 수 있는 것이 아닌 해당 빨간색 원이 있는 칸만 제외할 수 있다.

 

# 문제에서 최대 기쁨이 1000으로 제한뒀기 때문
low = 1000
position = [-1, -1]

for i in range(r):
    # 짝수 행이라면
    if i % 2 == 0:
    	# 홀수 칸만 지정
        for j in range(1, c, 2):
            if low > ground[i][j]:
                low = ground[i][j]
                position = [i, j]
    # 홀수 행이라면
    else:  # i % 2 == 1
    	# 짝수 칸만 지정
        for j in range(0, c, 2):
            if low > ground[i][j]:
                low = ground[i][j]
                position = [i, j]

이러한 부분이 제외할 칸 중 가장 적은 숫자(기쁨)을 찾는 로직이다.

 

제외할 칸을 찾았다면 그 부분만 피해서 이동을 하기 시작해야한다.

제외할 수 있는 칸 중 가장 적은 숫자인 1을 찾아냈고 그 좌표(0, 1)만 피해서 이동을 하면 된다.

 

res = ('D' * (r - 1) + 'R' + 'U' * (r - 1) + 'R') * (position[1] // 2)

제외할 칸의 x(열) 기준 // 2를 해서 먼저 이동을 해준다. 현재, 예제에서는 제외할 칸의 좌표가 (0, 1)이기 때문에 res에는 아무것도 들어가 있지 않다.

 

만약, 제외할 칸의 x가 (0, 1)이 아니라면?

이러한 이동이 되는 것이다. position의 값은 [0, 3]일 것이고, 3 // 2 = 1이기 때문에 한 번만 반복을 해서 저러한 결과가 나온다. (만약 1번만 반복했는데 어떻게 3칸이나 오른쪽으로 갔지? 생각한다면 1번 print부분을 다시 보면 된다.)

 

# 홀수를 짝수로 만들어준다.
# ex) 2 * (5 // 2) = 4
x = 2 * (position[1] // 2)
# y는 무조건 위에서 시작하기 때문에 0
y = 0
# 홀수를 짝수로 만들어준다음 무조건 오른쪽 1칸을 이동해야하는 과정이 있기 때문에
# xbound에다가 +1 해서 넣어줌
xbound = 2 * (position[1] // 2) + 1

# x와 xbound가 같고, y가 맨 밑 칸까지 갔다면 멈춤
while x != xbound or y != r - 1:
    # x가 xbound보다 왼쪽에 있고 [y, xbound]와 position의 값이 틀리다면 오른쪽 이동
    if x < xbound and [y, xbound] != position:
        x += 1
        res += 'R'
    # x가 xbound랑 값이 같으며, [y, xbound]와 position의 값이 틀리다면 왼쪽 이동
    elif x == xbound and [y, xbound - 1] != position:
        x -= 1
        res += 'L'
    # 마지막 줄이 아니라면 아래쪽으로 이동
    if y != r - 1:
        y += 1
        res += 'D'

사실상 x와 y가 이동한 칸의 좌표역할을 하여 이동을 제어하는 것이다.

if문을 자세히 좀 더 자세히 봐보자.

if x < xbound and [y, xbound] != position:
    x += 1
    res += 'R'

x가 xbound보다 작다면 x가 왼쪽 칸에 있다는 뜻이고, 오른쪽이 피해가야 할 칸이 아니면 오른쪽 이동을 하는 것이다. 그리고 오른쪽으로 이동했으니 x를 +1 해준다.

 

elif x == xbound and [y, xbound - 1] != position:
    x -= 1
    res += 'L'

x가 xbound랑 값이 같다면 x가 오른쪽 칸에 있다는 뜻이고, 왼쪽이 피해가야 할 칸이 아니면 왼쪽 이동을 하는 것이다.

그리고 왼쪽으로 이동했으니 x를 -1 해준다.

 

if y != r - 1:
    y += 1
    res += 'D'

현재 y가 r - 1칸이 아니라면 즉, y가 마지막 줄이 아니라면 아래로 이동하는 것이다.

그리고 아래쪽으로 이동했으니 y를 +1 해준다.

 

# (c - position[1] - 1) // 2
# 이동해야하는 나머지 칸 // 2
res += ('R' + 'U' * (r - 1) + 'R' + 'D' * (r - 1)) * ((c - position[1] - 1) // 2)

여기까지 다 봤다면 사실상 이코드는 왜 이렇게 되는지는 잘 이해될 것이다.