[그리디 알고리즘] ★ 2873번 - 롤러코스터

[백준] 2873번 - 롤러코스터

풀이 시간: 6~7 시간

 

1) 문제 해결 아이디어

아이디어를 떠올리는데 어려움을 겪은 문제다.

케이스를 분류하고 일반화하기가 까다로운 문제로 지금까지 풀었던 그리디 문제 중에는 제일 어려운 문제인 것 같다. 특히나 r, c가 모두 짝수인 경우가 구현하기 가장 까다롭기 때문에 푸는데 실패를 계속 겪고 정답이 되기까지 시간이 오래걸렸다.

 

각 칸은 한 번만 방문할 수 있고 지나간 칸의 합이 가장 최대가 되는경로를 출력하는 문제다.

지나간 칸의 합이 가장 최대가 되기 위해서는 최대한 많은 칸을 지나가야한다. 

 

이 문제는 r, c가 짝수인지 홀수인지에 따라서 케이스를 분리하는 것이 중요 포인트다.

3번째 케이스같은 경우는 제외할 1칸을 어떻게 설정할지를 떠올리는 것이 중요하다. 그 칸을 제외한 이동 경로를 설정하는 것이 쉽지 않았다.

 

<경우의 수>

1. r: 홀수, c: 짝수 or r: 홀수, c: 홀수

2. r: 짝수, c: 홀수

3. r: 짝수, c: 짝수

 

1. r: 홀수

r이 홀수일 때는 c의 값과 상관없이 동일한 케이스이다.

R D L D (r // 2)번 반복 후, R 1번

R (c-1)번

D 1번

L (c-1)번

D 1번

R (c-1)번

 

2. r: 짝수, c: 홀수

D R U R (c // 2)번 반복 후, D 1번

D (r-1)번

R 1번

U (r-1)번

R 1번

D (r-1)번

 

 

3. r: 짝수, c: 짝수

해당 케이스에서는 어느 경로든 간에 무조건 1칸은 가지 못한다.

그러므로 못가는 1개의 칸의 값이 최소가 되면 지나간 칸의 합이 최대가 된다.

 

1) 최솟값 찾기

못가는 칸의 경우는 아래와 같이 색칠된 칸들로 한정되어있다.

2) 3영역으로 구분하기

1) 빈칸 전, 2)  빈칸 포함, 3) 빈칸 후

3개의 영역으로 구분한다.

 

3) 영역별 경로 계산

 

 

첫번째 오류. 빈칸 포함 경로(2번 경로)

2번 경로에서 if문을 통해 R, L, D 중 무엇을 선택할지 결정하는 과정에서

마지막 if문을 elif문으로 검사해서 무한루프가 계속 돌면서 제대로 동작하지 않아 시간초과가 떴다.

elif문으로 코드를 짜면 예를 들어, 시작 좌표가 (0,2), 현재 좌표가 (0, 3), 최솟값 좌표가 (2, 3)이면 

1-2 조건이 참이므로 왼쪽으로 가게된다. (원래는 아래로 가야함)

그렇게 왼쪽, 오른쪽을 계속 반복하여 RLRLRLRL.... 이런식으로 무한루프에 빠지게 된다.

 

무엇보다 오랜 시간이 걸리더라도 설계를 정확히하는게 중요하다는 것을 다시 한번 느꼈다.

if문 같은 경우는 위치만 원하는 결과가 나오지 않을 수 있으므로 다시 한번 더 주의를 기울일 필요가 있다!

 

2) 소스코드

import sys

r, c = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(r)]
route = ""  # 경로
# r: 홀수, c: 짝수 / r: 홀수, c: 홀수
if(r % 2 != 0):
  route = ('R' * (c - 1) + 'D' + 'L' * (c - 1) + 'D') * (r // 2) + 'R' * (c - 1)
# r: 짝수, c: 홀수
elif(r % 2 == 0 and c % 2 != 0):
  route = ('D' * (r - 1) + 'R' + 'U' * (r - 1) + 'R') * (c // 2) + 'D' * (r - 1)
# r: 짝수, c: 짝수
elif(r % 2 == 0 and c % 2 == 0):
  min = 1000  # 최솟값
  min_x = -1
  min_y = -1
  # 최소값 위치 찾기
  for i in range(r):
    for j in range(c):
      # 짝수행에 대하여 
      if((i % 2 == 0 and j % 2 != 0) or (i % 2 != 0 and j % 2 == 0)):
        if(min > arr[i][j]):
          min = arr[i][j]
          min_x = i
          min_y = j
  # 1. 빈 칸 이전 열에 대한 경로(DRUR)
  route += ('D' * (r - 1) + 'R' + 'U' * (r - 1) + 'R') * (min_y // 2)
  #route += " "    
  
  # 2. 빈 칸을 둘러싼 경로
  y1 = (min_y // 2) * 2      # 첫번째 열
  y2 = (min_y // 2) * 2 + 1  # 두번째 열
  x = 0    # 2번 경로 시작 행
  y = y1   # 2번 경로 시작 열
  
  while True:
    # 마지막 행, 두번째 열이면 탈출
    if(x == r - 1 and y == y2):
      break
    # 1-1.현재 첫번째 열이고 오른쪽 칸이 빈칸이 아니면 오른쪽으로
    if(y == y1 and [x, y2] != [min_x, min_y]):
      route += 'R'
      y += 1
    # 1-2. 현재 두번째 열이고 왼쪽 칸이 빈칸이 아니면 왼쪽으로
    elif(y == y2 and [x, y1] != [min_x, min_y]):
      route += 'L'
      y -= 1
    # 2. 마지막 행이 아니면 아래로
    if(x != r - 1):
      route += 'D'
      x += 1
  #route += " "   

  # 3. 빈 칸 이후 열에 대한 경로(RURD)
  route += ('R' + 'U' * (r - 1) + 'R' + 'D' * (r - 1)) * ((c - min_y - 1) // 2)
  
print(route)

 

[참고] https://suri78.tistory.com/148

[백준알고리즘] 2873번: 롤러코스터 -Python