(Python) 백준 2873. 롤러코스터

문제

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

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

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

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

상세보기

• 세 가지 경우를 달리 생각해서 구현해야 하는 문제
• DFS를 사용한 완전탐색의 경우 시간초과가 발생한다.

• 가로나 세로 중 하나라도 홀수일 경우, 모든 칸을 탐색할 수 있지만
• 그 이외의 경우에는, 한 칸 이상을 제외해야 한다.
• 가로와 세로의 합이 짝수인 칸은, 제외하는 데에 한 칸 이상의 칸이 필요하다.
  
• 그림과 같이 가로와 세로의 합이 홀수인 칸만 탐색하여, 값이 가장 작은 칸을 제외하고 탐색하는 방식으로 구현하였다.

from sys import stdin; input=stdin.readline

N, M = map(int,input().split()) # X값과 Y값 가져오기
field = [tuple(map(int,input().split())) for _ in range(N)] # 롤러코스터가 움직일 레일 구성하기

res = ''
if N%2: # N이나 M 둘 중 하나가 홀수이면 무조건 전체를 돌 수 있음
    for i in range(N):
        if not i%2 :
            res += ('R'*(M-1) + 'D')
        else:
            res += ('L'*(M-1)+'D')


elif M%2: # N이나 M 둘 중 하나가 홀수이면 무조건 전체를 돌 수 있음
    for i in range(M):
        if not i%2 :
            res += ('D'*(N-1)+'R')
        else:
            res += ('U'*(N-1)+'R')


else: # 가로와 세로가 모두 짝수일 경우, 제외할 칸을 탐색해야 함
    min_val = 1000 # 가장 작은 값을 찾아야 하기 때문에 맥스 값을 넣어둠. 문제에서는 1000보다 작은 양의 정수라고 명시되어 있음
    min_x, min_y = -1, -1 # 최소점의 좌표를 기록해둘 변수
    for i in range(N):
        for j in range(M):
            if (i+j)%2:
                if field[i][j] < min_val:
                    min_val = field[i][j]
                    min_x, min_y = i, j
    catch = 0                   # 최소점이 있는 좌표를 확인했는지를 나타내는 변수(flag)
    for i in range(0,N,2):
        if i == min_x or i == (min_x-1): # 이 줄이나 아랫줄에 최소점이 있으면
            catch = 1
            find = 0
            y = 0
            while y != M-1:
                if i == min_x-1 and y == min_y: # 현재 지점의 아래가 최소점일 경우
                    res += 'RD'
                    y += 1
                    find = 1
                    
                elif i == min_x and y == min_y-1: # 현재 지점의 오른쪽이 최소점일 경우
                    res += 'DR'
                    y += 1
                    find = 1

                else:
                    if not find:
                        res += 'DRUR'
                        y += 2
                    else:
                        res += 'RURD'
                        y += 2
            res += 'D'
                
        else:
            if catch == 0:  # 좌표를 확인하지 못했을 경우 오른쪽 먼저 감
                res += ('R'*(M-1) + 'D' + 'L'*(M-1) + 'D')
            else:           # 좌표를 확인했을 경우 왼쪽을 먼저 감
                res += ('L'*(M-1) + 'D' + 'R'*(M-1) + 'D')

print(res[:-1]) # 마지막에 D가 추가되어있으므로 해당 D를 제외한 정답을 출력

• 길이가 짝수라는 게 확정이므로, 두 줄씩 묶어서 생각하였고
• 찾았을 경우와 찾지 못했을 경우의 움직임을 다르게 하도록 flag들을 사용하였다.