2873번 : 롤러코스터 - Python

문제

https://www.acmicpc.net/problem/2873

풀이

이 문제는 3가지 경우로 나눠서 볼 수 있다.

1. r이 홀수일때
r이 홀수라면 모든 부지를 방문할 수 있다. 단 $ㄹ$자 모양으로 방문하여야 한다.

2. c가 홀수일때
c가 홀수여도 모든 부지를 방문할 수 있다. 단 $N$자 모양으로 방문하여야 한다.

3. r, c둘다 짝수일때
r, c둘다 짝수라면 최소 한군대는 방문하지 못한다. 부지를 체스판으로 비유했을때 시작과 끝을 흰색판으로 둬보자, 거기서 검은색 칸에서의 최솟값이 방문하면 안되는 칸이다. 흰색칸에서 방문하지 않는 칸을 찾는다면 1칸 이상이 나온다.

코드

from sys import stdin

input = stdin.readline

r, c = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(r)]

if r%2!=0:
    str = 'R'*(c-1) + ('D' + 'L'*(c-1) + 'D' + 'R'*(c-1))*(r//2)
    print(str)
elif c%2!=0:
    str = 'D'*(r-1) + ('R' + 'U'*(r-1) + 'R' + 'D'*(r-1)) *(c//2)
    print(str)
else: 
    lowest = 1001  # 가장 작은 값을 찾기위해 설정 기쁨점수는 1000보다 작은 양의 정수이다.
    lowPosition = [-1, -1]  # 가장 작은 값의 위치
   
    #최소값과 위치 찾기
    for i in range(r):
        if i % 2 == 0:  # 짝수 행 이면 홀수칸만 본다.
            for j in range(1, c, 2):
                if lowest > arr[i][j]:
                    lowest = arr[i][j]
                    lowPosition = [i, j]
        else:  # 홀수 행 이면 짝수칸만 본다.
            for k in range(0, c, 2):
                if lowest > arr[i][k]:
                    lowest = arr[i][k]
                    lowPosition = [i, k]

    #피해갈 위치의 좌측최상단까지 간다.
    result = ("D" * (r - 1) + "R" + "U" * (r - 1) + "R") * (lowPosition[1] // 2)

    x = 2 * (lowPosition[1] // 2) # 홀수를 짝수로 만들어준다. , 시작점은 항상 짝수여야 하기때문이다.
    y = 0

    xbound = 2 * (lowPosition[1] // 2) + 1 #시작점의 x보다 하나 큰 것이 bound가 된다.

    #삭제할 위치의 가장 아래 오른쪽까지 간다.
    while x != xbound or y != r - 1:
        #끝이 아니고, 피할 위치가 아니면 오른쪽으로 간다.
        if x < xbound and [y, xbound] != lowPosition:
            x += 1
            result += 'R'
        #끝이고, 피할 위치가 아니면 왼쪽으로 간다.
        elif x == xbound and [y, xbound - 1] != lowPosition:
            x -= 1
            result += 'L'
        #가장 아래쪽이 아니면 내려간다.
        if y != r - 1:
            y += 1
            result += 'D'

    #도착지점까지 간다.
    result += ('R' + 'U' * (r - 1) + 'R' + 'D' * (r - 1)) * ((c - lowPosition[1] - 1) // 2)


    print(result)