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

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

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

2873번: 롤러코스터

문제의 규칙만 잘 생각하면 된다. 분류는 그리디 알고리즘으로 되어있으나 내가 푼 방식도 그리디 방법인지는 모르겠다. 가장 최소를 제거했으니 그리디인 건가?

 

문제에서 말하는 것은 최대한 많은 점수를 쌓기 위해서 최대한 많은 지점을 방문하라는 것이다. 결국에 다 방문할 수 있으면 다 방문하는 것이 최고의 방법이다.

그렇기 때문에 다 방문하지 못하는 경우가 존재할까? 생각해보면 된다.

 

우선 주어진 예제처럼 홀수의 행과 열의 개수라면 모두 방문할 수 있다.

아래의 그림들처럼 행 또는 열이 하나만 홀수가 되더라도 모든 지점을 방문할 수 있다.

열이 홀수개

행이 홀수개

 

하지만 행과 열이 모두 짝수개라면 모든 점을 방문할 수 없다. 하지만 한 점을 제외한다면 한 점을 제외한 모든 점을 방문할 수 있다. 따라서 가장 작은 한 점을 제외하고 모든 점을 방문하도록 하면 된다.

 

하지만 가장 작은 점을 아무거나 고르면 안 된다. 여기서 지점을 i, j (0 <= i <= r, 0 <= j <= c)라고 했을 때 i+j가 홀수인 지점만 선택할 수 있다. 즉 아래와 같은 격자모양의 평면이 완성이 된다. 여기서 형광펜을 칠한 부분 중 한 점을 제외하고 모든 점을 방문하는 경로를 구성할 수 있지만, 칠하지 않은 부분 중 한 점을 제외하고 모든 점을 방문하는 경로는 구할 수 없다.

칠하지 않은 점 중에 한 점을 제외하려면 형광펜을 칠한 한 점 또한 같이 제외를 시켜야 하는데, 그렇다면 형광펜을 칠한 그 한 점만 제외한 것이 더 높은 점수를 갖기 때문이다.

 

이러한 방식은 6x6처럼 행과 열의 개수가 같지 않아도 마찬가지이다. 따라서 저러한 지점들의 최소 지점을 구한 후 해당 지점을 방문하지 않도록 해주었다. 여러 방법들이 존재하지만 내가 구성한 방식은 아래와 같이 지나지 않을 지점이 포함된 묶음을 기준으로 3가지 방식으로 나눈 방법이다.

 

import sys
 
r, c = map(int, sys.stdin.readline().split())
ground = [list(map(int, sys.stdin.readline().split())) for _ in range(r)]
 
if r % 2 == 1:
    sys.stdout.write( ('R'*(c-1) + 'D' + 'L'*(c-1) + 'D')*(r//2) + 'R'*(c-1) )
elif c % 2 == 1:
    sys.stdout.write( ('D'*(r-1) + 'R' + 'U'*(r-1) + 'R')*(c//2) + 'D'*(r-1) )
elif r % 2 == 0 and c % 2 == 0:
    # find position to jump
    low = 1000
    position = [-1, -1]
    for i in range(r):
        if i % 2 == 0:
            for j in range(1, c, 2):
                if low > ground[i][j]:
                    low = ground[i][j]
                    position = [i, j]
        else: # i % 2 == 1
            for j in range(0, c, 2):
                if low > ground[i][j]:
                    low = ground[i][j]
                    position = [i, j]
    
    res = ('D'*(r-1) + 'R' + 'U'*(r-1) + 'R')*(position[1]//2)
    x = 2 * (position[1]//2)
    y = 0
    xbound = 2 * (position[1]//2) + 1
    while x != xbound or y != r - 1:
        if x < xbound and [y, xbound] != position:
            x += 1
            res += 'R'
        elif x == xbound and [y, xbound-1] != position:
            x -= 1
            res += 'L'
        if y != r-1:
            y += 1
            res += 'D'
 
    res += ('R' + 'U'*(r-1) + 'R' + 'D'*(r-1))*((c-position[1]-1)//2)
 
    print(res)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다