백준 1149 : RGB거리 (Python)

백준 1149 문제

문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1

26 40 83
49 60 57
13 89 99

예제 출력 1

96

---

아이디어

이 문제에서 제시하는 조건은 대략 2개로 정리할 수 있다.

1. 한 집과 인접한 집의 색은 다른 색이어야 한다.
2. 1번 규칙을 만족하되 최소 비용이어야 한다.

우선 첫번째 조건은 어떻게 체크할 수 있을까?

입력 받을 때부터 빨강, 초록, 파랑별로 행을 구분해 두었기 때문에 내가 다음에 검사할 집의 행 인덱스 숫자가 내 집과 다르면 된다.

그렇다면 두번째 조건에서 최소 비용인 것은 어떻게 파악할 수 있을까?

내 집의 다음 집과 행 인덱스 숫자가 다르면서 값이 최소인 것을 선택하는 방식을 처음으로 떠올릴 수 있겠지만 이는 적절하지 않다. 내가 하는 선택이 전체적인 측면에서 최대 이득이라는 보장이 없기에 그럴 것이다. 따라서 최소 비용을 어떻게 효율적으로 찾냐가 관건인 문제라고 볼 수 있다.

첫번째 풀이 : DFS + 완전 탐색

• 테스트 케이스 모두 맞았으나 시간초과
• DFS를 재귀로 구현함. 시작 노드가 colors[0][0], colors[0][1], colors[0][2] 인 3가지 경우 모두에 대해 DFS 수행해 최소값 출력함.
• N이 최대 1000으로 최악의 경우 3*(2**999)번 dfs 함수가 호출됨...

import sys 
sys.setrecursionlimit(10**6)

answers = []

def dfs(r,c,total):
    global answers,colors,N 
    total += colors[r][c] 
    if r == N-1:
        answers.append(total)
        return 
    else:
        for i in range(3):
            if i!= c:
                dfs(r+1,i,total)


N = int(sys.stdin.readline())
colors = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]

for i in range(3):
    dfs(0,i,0)
    
print(min(answers))
    

두번째 풀이 : 트리 DP

• 통과

• 시간복잡도는 O(N)으로 첫번째 풀이보다 훨씬 효율적이다.

• 이 문제는 완전 이진 트리로도 해석할 수 있다. 아래 코드에서는 첫번째 집을 칠하는 값이 말단 노드인 완전 이진 트리를 상정하고 풀이했다. 예제 입력 1의 경우, 마지막 행의 첫번째 열인 값을 루트 노드로 가진다면 아래 그림의 트리를 탐색하는 것과 같다. 결국 이 문제는 완전 이진 트리의 최소합을 구하는 문제이기에 부분적으로 반복되며 최적 부분 구조를 만족한다. 따라서 DP로 풀이하는 것이 적절할 것이다.
  

import sys 
sys.setrecursionlimit(10**6)

N = int(sys.stdin.readline())
colors = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
dp = [[0,0,0] for _ in range(N)]
# 말단 노드 값 == 말단 노드의 최소합  
dp[0][0], dp[0][1], dp[0][2] = colors[0][0],colors[0][1],colors[0][2]

for i in range(1,N):
    dp[i][0] = colors[i][0] + min(dp[i-1][1],dp[i-1][2])
    dp[i][1] = colors[i][1] + min(dp[i-1][0],dp[i-1][2])
    dp[i][2] = colors[i][2] + min(dp[i-1][0],dp[i-1][1])
    

print(min(dp[N-1]))