[백준 BOJ] 2873 롤러코스터 (python)

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

2873번: 롤러코스터

그리디 카테고리의 첫 문제 롤러코스터입니다.

사실 엄청나게 그리디한 문제도 아니며 플래티넘3 수준의 문제도 아닌 것 같습니다.

하지만 풀이하는 과정이 재밌었기에 이렇게 글로 남겨봅니다.

 

우선 행 혹은 열이 홀수인 경우 모든 칸을 완전탐색 가능합니다.

가장 흔하게 그러므로 가장 흔하게 완전탐색할 수 있는 S자 뱀모양으로 롤러코스터를 방문시키도록 합니다.

 

저희가 이후 생각해야 할 경우는 이제 행과 열이 모두 짝수인 경우입니다.

이 경우에는 완전탐색이 불가능하고, 이는 증명 가능합니다.

시작하는 점을 (1, 1)이라고 하고 이동은 한칸 씩 진행이 되므로 두 좌표의 합은 짝홀을 반복하게 됩니다.

행과 열이 짝수이므로 도착하는 점은 (짝수, 짝수)이므로 좌표의 합은 짝수이고, 따라서 합이 짝수인 칸을 홀수인 칸보다 하나 더 지나게 됩니다.

하지만 좌표의 합이 짝수인 칸과 홀수인 칸의 수는 같으므로 최소한 좌표의 합이 홀수인 칸 하나는 지나지 못하게 됩니다.

그러므로 저는 코드에서 좌표의 합이 홀수인 칸 중 롤러코스터 기쁨 수치가 최소인 칸을 x, y로 선택하였습니다.

 

이제는 (x, y)를 제외한 모든 칸을 방문할 수 있을지를 알아보아야 합니다.

여기서 그리디 비슷한 방식을 사용했습니다.

우선 행을 두줄씩 묶어 생각해주었습니다.

(x, y)를 포함한 행을 제외하고 다시 뱀모양으로 롤러코스터를 방문시키도록 합니다.

위 쪽의 행에서는 각 두 줄을 첫 열에서 끝 열로 갔다가 다시 첫 열로 돌아와 원래 열로 돌아오게 됩니다.

아래 쪽 행에서도 각 두 줄을 끝 열에서 첫 열로 갔다가 다시 끝 열로 돌아와 역시 원래 열로 돌아오게 됩니다.

그렇게 되면 결국 남은 경로는 (x, y)를 포함한 2행짜리 롤러코스터 문제가 됩니다.

이번에는 열을 두줄씩 묶어 생각해줍니다.

역시 (x, y)를 포함한 열을 제외하고 뱀모양으로 방문이 가능합니다.

최종적으로는 (x, y)를 포함한 2행 2열의 롤러코스터 문제만 남게 됩니다.

이때 x, y값의 홀짝에 따라 DR로 진행할지 RD로 진행할지만 정해주시면 됩니다.

이러한 식으로 (x, y)를 제외한 모든 칸을 방문할 수 있고, 이런 방문이 가장 큰 기쁨을 주는 롤러코스터 경로가 됩니다. 

 

import sys

R, C = map(int, sys.stdin.readline().rstrip().split())
ans = ''
if R % 2:
    ans += ('R' * (C-1) + 'D' +'L' * (C-1) + 'D') * (R // 2) + 'R' * (C-1)
elif C % 2:
    ans += ('D' * (R-1) + 'R' +'U' * (R-1) + 'R') * (C // 2) + 'D' * (R-1)
min_n = 1001
for i in range(R):
    line = list(map(int, sys.stdin.readline().rstrip().split()))
    for j in range(C):
        if (i + j) % 2 and line[j] < min_n:
            min_n = line[j]
            x = i
            y = j
if not ans:
    ans += ('R' * (C-1) + 'D' +'L' * (C-1) + 'D') * (x // 2)
    ans += 'DRUR' * (y // 2)
    if y % 2:
        ans += 'DR'
    else:
        ans += 'RD'
    ans += 'RURD' * (C // 2 - y // 2 - 1)
    ans += ('D' + 'L' * (C-1) + 'D' +'R' * (C-1)) * (R // 2 - x // 2 - 1)
print(ans)