[BOJ] 2873 롤러코스터

thoho·2023년 1월 7일

코딩 문제 풀이

목록 보기

3/13

2873. 롤러코스터 문제 링크
정답 코드 링크
플래티넘을 너무 만만하게 본 것인가. 꽤나 한참동안 헤맸던 문제. 특정 알고리즘이 어려웠다기 보다는 문제를 풀기 위한 아이디어를 떠올리고 규칙을 찾아야했던 문제였어서, 관련 부분에서 헤맸던 것 같다.

그리디 알고리즘

매 선택마다 가장 가능성이 높아보이는 선택을 하고, 선택이 유효한지 검사하며 해답을 찾는 알고리즘.

문제 요약

R * C 크기의 행렬이 주어지고, 왼쪽 맨 위에서 출발해 오른쪽 맨 아래까지 도달할 때 까지 거쳐온 칸의 값의 합이 최대가 되도록 이동할 수 있는 경로를 구하는 것이다.

설명

돌아온 값의 합이 최대가 되려면, 직관적으로 최대한 많은 칸을 방문해야하며, 방문하지 못하는 칸은 값이 작을수록 좋다.

문제를 해결하기 위해서는 다음과 같은 경우로 입력 케이스를 나누어볼 수 있다.

(A) R과 C 둘 중 하나라도 홀수

즉, R % 2 == 1 or C % 2 == 1인 경우.
이 경우 간단한 경로로 [0][0]에서 출발해 [R-1][C-1]에 모든 칸을 거쳐 도달하는 것이 가능하다.

(B) R과 C 모두 짝수

이 경우 모든 칸을 순회하는 것은 불가하다. 그렇다면 몇 개의 칸을 방문할 수 없는지 생각해보자.

최소 1개이다. 적어도 1개의 칸은 방문할 수 없다. 그렇다면 주어진 행렬에서 가장 값이 작은 한 칸을 밟지 않고 지나가도록 코드를 구현하면 되지 않을까?
이 가설이 맞는지 확인을 해보니, 피하려는 칸의 위치에 따라 밟지 못하는 칸의 수가 달라졌다.

1칸만 피할 수 있는 특정 칸이 따로 존재한다.

피하려는 1칸이 위와 같이 X가 표시된 위치일 때, 즉 (i + j) % 2 == 1를 피하려고 할 때에만 R*C - 1개의 칸을 지나갈 수 있다. 이 시점에서 다음을 고민했다.

위에 해당하는 1칸만 피하는 것이 무조건적으로 이득인가?

즉, 위의 조건을 만족하는 5짜리 칸을 지나지 못하는 것보다 1, 1, 1을 지나가지 못하는 경우가 더 이득일 수 있지 않은가?

그래서 이것저것 비교해보니, 피하려는 칸이 어느 칸이든 필연적으로 위의 조건((i + j) % 2 == 1)에 해당하는 칸을 지날수밖에 없었다. 해당 칸을 포함하는 여러칸을 지나가지 않는 것보다, 해당 칸만을 지나지 않는 것이 더 이득임은 당연하다.

따라서, 조건을 만족하는 칸 중 가장 값이 작은 칸을 선택해서 지나가지 않는 경로를 구현하면 된다.

구현

입력 받기

R, C = map(int, input().split(" "))

field = []
minValue = 1e9
minCoordinate = None

for i in range(R) :
  field.append(list(map(int, input().split(" "))))
  for j in range(C) :
    if (i + j) % 2 == 1 and minValue > field[i][j] :
      minValue = field[i][j]
      minCoordinate = (i, j)

입력을 받으며 피해야하는 1칸을 함께 찾아주었다. 조건을 만족하는 칸이 최소값일 경우 해당 좌표를 minCoordinate 변수에 넣어주었다.

조건 분기

if R % 2 == 1 :
  answer = oddCase(dir, 'R', 'D', R, C)
elif C % 2 == 1 :
  answer = oddCase(dir, 'D', 'R', R, C)
else :
  answer = evenCase(R, C, minCoordinate[0], minCoordinate[1])

R이 홀수일 경우 ㄹ모양으로 이동하는 경로를 출력하면 된다. 만일 R이 짝수이고 C가 홀수일 경우 경로를 x=y에 대칭시켜서(설명을... 어떻게 해야하나...), 즉, 아래->위->아래를 번갈아가며 이동하는 경로를 출력하면 된다. 상단 첫번째 이미지 참고.

R과 C 둘 중 하나라도 홀수인 경우


# 이동 방향에 따른 좌표 변환 수치.
dir = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)} 

# 방향을 전환했을 때의 방향을 반환
def reflect(dir) :
  if dir == 'R' :
    return 'L'
  elif dir == 'L' :
    return 'R'
  elif dir == 'D' :
    return 'U'
  elif dir == 'U' :
    return 'D'

# R과 C 둘 중 하나라도 홀수인 경우 해당 경로를 string으로 반환해주는 함수.
# - dir: 이동하는 방향에 해당하는 좌표 변환을 대응해주는 dictionary.
# - nextLevel : 다음 줄로 이동할 때에 해당하는 방향.
#				R과 L로 번갈아 움직일 때에는 D,
#				D와 U로 번갈아 움직일 때에는 R
def oddCase(dir, firstDir, nextLevel, R, C) :
  answer = []
  curDir = firstDir
  x, y = 0, 0

  while True :
  	# 다음에 이동하려는 좌표
    nextY = y + dir[curDir][0]
    nextX = x + dir[curDir][1]
    
    # 이동하려는 좌표가 종료 지점인 경우, 해당 경로를 추가하고 종료
    if (nextY, nextX) == (R-1, C-1) :
      answer.append(curDir)
      break
    
    # 이동하려는 좌표가 out of index인 경우 경로 수정
    if nextY < 0 or nextY >= R or nextX < 0 or nextX >= C :
      answer.append(nextLevel) # 다음 줄로 이동
      y = y + dir[nextLevel][0]
      x = x + dir[nextLevel][1]
      curDir = reflect(curDir) # 방향 수정
    else : # out of index가 아닌 경우 현재 방향대로 그대로 이동. 
      answer.append(curDir)
      y = nextY
      x = nextX
  return ''.join(answer)

L↔R 이동할때와 U↔D 이동할때 다른 코드를 짜고 싶지 않아서 발악하다보니... 조금은 복잡한 코드가. parameter중 nextLevel에 대해 보충설명을 하자면, 주 이동 경로를 따라 이동하다 다음 줄로 이동할 때에 해당하는 문자이다.

R과 C 모두 짝수인 경우

def evenCase(R, C, avoidY, avoidX) :
  isAvoided = False
  answer = []

  for i in range(R // 2) :
    if avoidY == i * 2 or avoidY == i * 2 + 1 :
      answer.append(move2line_zigzag(C, avoidY - i * 2, avoidX))
      isAvoided = True
    else :
      if isAvoided :
        answer.append(move2line_straight(C, 'L'))
      else :
        answer.append(move2line_straight(C, 'R'))
    
    if i != (R // 2) - 1 :
      answer.append('D')

  return ''.join(answer)

두 줄 단위로 나누어서 순회하는 것으로 구현하였다.

피하려는 칸이 이 두 줄의 범위에 포함될 경우, 위아래 지그재그 방향으로 이동하며 해당 좌표를 피한다.
피하려는 칸이 이 두 줄의 범위에 포함되지 않을 경우, ㄷ 모양 혹은 コ 모양으로 순회한다.
(1) 피하려는 칸을 앞에서 이미 피한 경우, ㄷ 모양으로 순회한다.
(2) 피하려는 칸을 아직 피하지 않은 경우, コ 모양으로 순회한다.

피하려는 좌표의 y 좌표는 2줄의 좌표에 맞추어서 변환해주어 넘겨주었다.
ex. avoidY가 3인 경우, 1로 변환해주었다.

def move2line_straight(C, firstDir) :
  answer = []
  curDir = firstDir
  for i in range(C-1) :
    answer.append(curDir)
  answer.append('D')
  curDir = reflect(curDir)
  for i in range(C-1) :
    answer.append(curDir)
  
  return ''.join(answer)

ㄷ자 혹은 コ자로 이동하는 코드. firstDir이 처음 이동하는 방향이다.

def move2line_zigzag(C, avoidY, avoidX) :
  answer = []
  curDir = 'D'
  x, y = 0, 0
  while True :
  	# 다음에 이동하려는 좌표
    nextY = y + dir[curDir][0]
    nextX = x + dir[curDir][1]
	
    # 이동하려는 좌표가 피하려는 칸일 경우, 해당 좌표로 이동하지 않고 다음 칸으로 넘어간다.
    if (nextX, nextY) == (avoidX, avoidY) :
      answer.append('R')
      x += 1
    # 이동하려는 좌표가 종료되는 좌표일 경우(우측 아래) 이동하고 종료
    elif (nextX, nextY) == (C - 1, 1) :
      answer.append(curDir)
      break
    # 이동하려는 좌표로 이동이 가능한 경우. 
    # 두 줄에 거쳐서 지그재그로 움직이기 때문에 이동 직후 다음 칸으로 이동하고 방향을 전환해준다.
    else :
      x = nextX + 1
      y = nextY
      answer.append(curDir) # 현재 방향으로 이동
      answer.append('R') # 다음 칸으로 이동
	  
      # 다음 칸이 종료 조건일 경우 종료
      if (x, y) == (C - 1, 1) :
        break
		
      curDir = reflect(curDir) # 방향 전환


  return ''.join(answer)