[백준 1149] RGB거리 (Python)

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

1st Attempt (Failed) - 런타임 에러(RecursionError)

import sys

dp = [[-1 for _ in range(3)] for _ in range(1000)]
def find(prev, i):
    if i >= n:
        return 0

    if prev is not None and dp[i][prev] != -1:
        return dp[i][prev]

    rgb = [0,1,2]
    if prev is not None:
        rgb.pop(prev)

    answer = min([array[i][j] + find(j, i+1) for j in rgb])
    if prev is not None:
        dp[i][prev] = answer
    return answer

def solution(n, array):
    return find(None, 0)

n = int(sys.stdin.readline())
array = [[int(i) for i in sys.stdin.readline().rstrip().rsplit()] for _ in range(n)]
print(solution(n, array))

1000개 집에 대해 재귀 호출하며 최소비용을 계산한다.

그런데 Python에서 재귀 호출 일정 횟수 이상 일어나면 RecursionError가 발생한다.

백준에서는 최대 재귀 호출 횟수가 1000회로 지정되어있다. 따라서 최대 1000개의 집에 대해 재귀적으로 계산하면 에러가 발생할 수 있다.

문제 해결을 위해 재귀적 방법이 아닌 반복문을 이용한 반복적 동적 계획법을 적용해야 한다.

2nd Attempt (Succeed)

import sys

dp = [[0 for _ in range(3)] for _ in range(1001)]

def solution(n, array):
    for i in range(1, n + 1):
        current = array[i-1]
        for j in range(3):
            index = [0,1,2]
            index.pop(j)
            dp[i][j] = min(dp[i-1][k] + array[i-1][j] for k in index)

    return min(dp[n])

n = int(sys.stdin.readline())
array = [[int(i) for i in sys.stdin.readline().rstrip().rsplit()] for _ in range(n)]
print(solution(n, array))

(algorithm-problem-solving/1149.py at main · simba3447/algorithm-problem-solving)[https://github.com/simba3447/algorithm-problem-solving/blob/main/baekjoon/1149/1149.py]

반복적 동적 계획법을 활용해 Bottom-Up 방식으로 문제를 해결했다.

기저 사례부터 optimal한 값을 모두 계산해 타고 올라가며 이전 계산값을 활용해 최적해를 계산한다.

함수의 재귀 호출 대신 반복문을 활용하므로 재귀 호출로부터 오는 스택 오버플로의 위험이 없다.

후기

이전에 함수의 재귀 호출을 활용하는 방식으로 동적계획법을 사용하는 데에 익숙해져 있었는데 제약조건에 의해 반복적 재귀 호출의 사용이 필요한 문제를 만났다. 완전탐색을 시도하거나 동적계획법을 구현할때 입력 범위를 보고 재귀 호출의 깊이를 고려해 구현 전략을 택해야 할듯하다.