롤러코스터 (BOJ 2873)

처음으로 풀어본 구현 문제… 구현 문제 어렵다 ..

끝까지 풀지 못하고 해석을 봐야했다. (https://seungyong20.tistory.com/39)

• 원리를 완벽히 파악하지 못했다. (격자 칸들만 제외할 수 있다는 걸 깨닫지 못함)
• 원리를 파악했다고 하더라도, 구현에 대한 노하우가 부족했음
• 무작정 플레 난이도에 도전해봤는데, 아직까진 역시 내 수준이 부족함을 깨닫게 해준 문제이다

최종 풀이

# 가능하다면 모든 칸을 다 먹어야 한다
# R = 홀수 or C = 홀수일 경우 모든 칸 먹기 가능
# R = 홀수라면 ㄹ 형태, C = 홀수라면 뒤집힌 ㄹ 형태

# R, C가 모두 짝수라면 한 칸을 버려야 한다
# 문제: 1) 어느 칸을 버려야 하는가? 2) 화살표 구현

import sys

R, C = map(int, input().split())
land = [[0 for i in range(C)] for j in range(R)]

for i in range(R):
    land[i] = list(map(int, sys.stdin.readline().split()))

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: # 여러 칸 중 하나 제외
    lowest = 1000
    location = [-1, -1] # 제외할 칸의 좌표

    for i in range(R): # 제외할 칸(기쁨이 가장 낮은 칸) 고르기
        if i % 2 == 0: # 짝수행 중에서
            for j in range(1, C, 2): # 홀수열들이 후보
                if lowest > land[i][j]:
                    lowest = land[i][j]
                    location = [i, j]
        else:  # 홀수행 중에서
            for j in range(0, C, 2): # 짝수열들이 후보
                if lowest > land[i][j]:
                    lowest = land[i][j]
                    location = [i, j]
    
    res = ('D'*(R-1) + 'R' + 'U'*(R-1) + 'R')*(location[1]//2) # 제외할 칸에 닿기 전 line까지 위아래로 훑기
    
    # 제외 칸 피해가기 구현 (x,y 좌표가 0에서 시작함을 헷갈리지 말자)
    ## x좌표가 제외칸, 제외칸-1 에 있는 두 줄은 ㄹ을 그리며 통과한다
    ## 그 외 구간은 up&down으로 통과한다. 
    
    x = 2*(location[1]//2) # 현재 위치의 x좌표
    y = 0 # 현재 위치의 y좌표 - 무조건 맨 위에서 시작 
    xColumn = 2*(location[1]//2) + 1

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

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

    print(res)

1. 전체 land의 크기가 R=홀수 또는 C=홀수를 만족하면 무조건 모든 칸을 먹을 수 있다.
   • 그대로 구현 해주면 됨 (ㄹ 형태 또는 up&down)
2. 문제는 R, C 가 모두 짝수인 경우이다.
   • 이때는 반드시 한 칸은 포기해야 한다.
   • 이때, 빨간 원에 해당하는 칸만 제외할 수 있다.
     • 하얀 칸 두개 제외하는게 나은 경우도 있지 않나?
       • 하얀 칸을 고르면 여러 칸을 제외하게 된다. 그리고 필연적으로 빨간 원도 그 안에 포함되게 되므로, 굳이 그럴 필요 없이 빨간 원만 하나 제외하는 것이 깔끔하다. (물론 그게 최댓값이다)
3. 우선 어떤 칸을 제외할지를 정해야 한다.
   • 위 빨간 원들끼리만 비교해주면 된다
     • 기쁨의 크기가 가장 낮은 칸의 위치를 location = [x, y] 로 저장해준다
4. 제외칸을 피해가는 경로를 구현한다

A. 제외칸 직전까지는 up&down으로 접근한다

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

• 이를 거치고 나면, 탑승자는 제외칸의 location 좌표에 따라 아래 초록칸 중 하나에 위치하게 된다.
  • 제외칸은 x축 기준으로 1) 탑승자와 같은 line에 있거나, 2) 한 칸 오른쪽에 있게 된다

B.ㄹ 자 모양으로 제외칸을 피해간다

• 제외칸의 x좌표를 기준선으로 두고, 좌우로 왔다갔다 하면서 통과하면 된다
• 맨 아래까지 그렇게 통과한다

x = 2*(location[1]//2) # 현재 위치의 x좌표
y = 0 # 현재 위치의 y좌표 - 무조건 맨 위에서 시작 
xColumn = 2*(location[1]//2) + 1 # 제외할 칸의 x좌표. 기준선이 된다.

while x != xColumn or y != R-1: # x좌표는 기준선을 넘지 않아야 하며, y좌표는 바닥을 뚫고 나갈 수 없다. 
    if x < xColumn and [y, xColumn] != location:
        x += 1
        res += 'R'
    elif x == xColumn and [y, xColumn-1] != location:
        x -= 1
        res += 'L'
    if y != R-1:
        y += 1
        res += 'D'

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

C. 제외칸을 통과한 나머지는 다시 up&down으로 도착지까지 간다.

이 코드가 작동하는 과정을 그림으로 표현하면 다음과 같다.