[백준] 2873번 롤러코스터 - Python / 알고리즘 중급 1/3 - 그리디 알고리즘 (도전)

ByungJik_Oh·2025년 6월 27일

Baekjoon Online Judge

[Baekjoon Online Judge]

목록 보기

172/244

💡 문제

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

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

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

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

입력

첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.

출력

첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.

💭 접근

처음 이 문제를 접했을 땐 그리디 문제로 분류되어 있지만 백트래킹으로 간단하게 구현할 수 있을 것이라고 생각했고, 백트래킹으로 구현한 결과 메모리 초과가 발생하였다.(아마 움직이는 방향을 저장하는 과정에서 발생한 것 같다.) 따라서 다른 방법을 찾게 되었고, 이 문제는 행과 열의 경우에 따라 그리디하게 해결할 수 있다는 것을 알게 되었다.

이 문제는 2가지 경우로 나뉘게 된다.

R(행) 또는 C(열) 둘 중 하나라도 홀수인 경우

위 그림처럼 행 또는 열 둘 중 하나라도 홀수인 경우에는 모든 칸을 방문할 수 있으므로 입력으로 주어진 r과 c에 맞게 다른 연산없이 그대로 출력해주면 된다.

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))

R(행)과 C(열)이 모두 짝수인 경우

위 그림처럼 행과 열이 모두 짝수인 경우에는 반드시 한칸을 제외하고 이동해야 목적지에 도착할 수 있는데, 이때는 아래 그림과 같이 검정색으로 색칠되어 있는 칸만 건너뛸 수 있다.

위 조건에서 가장 큰 기쁨을 얻을 수 있도록 하기위해선 검정색 칸 중 가장 적은 기쁨이 속하는 칸을 건너뛰고 모두 방문해주면 정답이 도출될 것이다.

그렇다면 어떻게 가장 작은 칸은 건너뛸 수 있을까?

 min_joy = 1000
 pos = [-1, -1]

 for i in range(r):
    if i % 2 == 0:
        for j in range(1, c, 2):
            if min_joy > joy[i][j]:
                min_joy = joy[i][j]
                pos = [i, j]
    else:
        for j in range(0, c, 2):
            if min_joy > joy[i][j]:
                min_joy = joy[i][j]
                pos = [i, j]

먼저 검정색 칸에 한해서 가장 작은 기쁨이 속하는 칸의 좌표를 찾는다.

좌표를 찾았다면, 우선 그 좌표가 해당하는 열 직전까지 이동해준다.

ans = ('D' * (r - 1) + 'R' + 'U' * (r - 1) + 'R') * (pos[1] // 2)

이제 가장 작은 기쁨이 속하는 칸이 포함되어있는 열에 도착하였다면 그 칸을 피해서 정답에 더해준다.

 x = 2 * (pos[1] // 2)
    y = 0
    xbound = x + 1

    while x != xbound or y != r - 1:
        if x < xbound and [y, xbound] != pos:
            x += 1
            ans += 'R'
        elif x == xbound and [y, xbound - 1] != pos:
            x -= 1
            ans += 'L'
        if y != r - 1:
            y += 1
            ans += 'D'

이제 가장 작은 기쁨이 속하는 칸을 포함하는 열을 지났으니 남은 칸들을 모두 방문해준다.

 ans += ('R' + 'U' * (r - 1) + 'R' + 'D' * (r - 1)) * ((c - pos[1] - 1) // 2)

🔥처음 제출한 코드 (백트래킹)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(cnt, pos, x, y):
    global ans_cnt, ans

    if x == r - 1 and y == c - 1:
        if cnt > ans_cnt:
            ans_cnt = cnt
            ans = pos
        return
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        n_move = pos + move[i]
        if 0 <= nx < r and 0 <= ny < c and visited[nx][ny] == 0:
            visited[nx][ny] = 1
            dfs(cnt + joy[nx][ny], n_move, nx, ny)
            visited[nx][ny] = 0

r, c = map(int, input().split())
joy = [list(map(int, input().split())) for _ in range(r)]
visited = [[0 for _ in range(c)] for _ in range(r)]
visited[0][0] = 1

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
move = ['U', 'D', 'L', 'R']

ans_cnt = 0
ans = ''

dfs(joy[0][0], '', 0, 0)

print(ans)

📒 코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
joy = [list(map(int, input().split())) for _ in range(r)]

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:
    min_joy = 1000
    pos = [-1, -1]

    for i in range(r):
        if i % 2 == 0:
            for j in range(1, c, 2):
                if min_joy > joy[i][j]:
                    min_joy = joy[i][j]
                    pos = [i, j]
        else:
            for j in range(0, c, 2):
                if min_joy > joy[i][j]:
                    min_joy = joy[i][j]
                    pos = [i, j]

    ans = ('D' * (r - 1) + 'R' + 'U' * (r - 1) + 'R') * (pos[1] // 2)
    x = 2 * (pos[1] // 2)
    y = 0
    xbound = x + 1

    while x != xbound or y != r - 1:
        if x < xbound and [y, xbound] != pos:
            x += 1
            ans += 'R'
        elif x == xbound and [y, xbound - 1] != pos:
            x -= 1
            ans += 'L'
        if y != r - 1:
            y += 1
            ans += 'D'
    
    ans += ('R' + 'U' * (r - 1) + 'R' + 'D' * (r - 1)) * ((c - pos[1] - 1) // 2)

    print(ans)