문제 소개
작은 도시에 일렬로 늘어선 m개의 집이 있다고 가정해 보겠습니다. 각 집은 n가지 색상(1부터 n까지 번호가 매겨짐) 중 하나로 반드시 칠해야 하며, 일부 집은 이미 칠해져 있어 다시 칠할 필요가 없습니다. 여기서 이웃(neighborhood)은 인접한 집들 중 같은 색으로 연속되어 묶인 그룹을 의미합니다.
배열 houses에서 houses[i]는 i번째 집의 현재 색상을 나타내고, 값이 0이면 아직 칠해지지 않았음을 뜻합니다. 2차원 배열 cost에서 cost[i][j]는 i번째 집을 j+1번 색으로 칠할 때 드는 비용입니다. 마지막으로 target은 결과적으로 만들어야 할 이웃 그룹의 정확한 개수입니다.
목표는 아직 칠하지 않은 집들을 모두 칠해서 정확히 target개의 이웃이 생기도록 하는 최소 비용을 찾는 것이며, 해가 존재하지 않는다면 -1을 반환해야 합니다.
예제
입력이 다음과 같다고 해봅시다.
- houses = [0,2,1,2,0]
- cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]
- n = 2
- target = 3
이미 칠해진 집이 있으므로 나머지 집을 [2,2,1,2,2] 형태로 칠하면 이웃은 {2,2}, {1}, {2,2}로 정확히 세 개가 됩니다. 첫 번째 집을 2번 색으로 칠하는 비용이 10, 마지막 집을 2번 색으로 칠하는 비용이 1이므로 총 비용은 10 + 1 = 11입니다.
풀이 접근 방법
이 문제는 재귀 함수를 이용해 풀 수 있습니다. 각 집을 차례대로 확인하면서, 아직 칠해지지 않은 집이라면 가능한 모든 색을 시도해 보고 그중 최소 비용을 선택하는 방식입니다. 단계별로 정리하면 다음과 같습니다.
- m := houses 배열의 크기
- helper(i, p_col, grp) 함수를 정의합니다. i는 현재 집의 인덱스, p_col은 이전 집의 색상, grp는 지금까지 만들어진 이웃 그룹의 수입니다.
- i가 m과 같으면(모든 집을 처리했으면), grp가 target과 같으면 0을, 아니면 무한대(inf)를 반환합니다.
- houses[i]가 0이 아니라면(이미 칠해진 집이라면), helper(i + 1, houses[i], grp + (p_col != houses[i]이면 1, 아니면 0))을 반환합니다.
- total := inf로 초기화합니다.
- col을 1부터 n까지 반복하면서, total을 min(total, cost[i][col-1] + helper(i + 1, col, grp + (p_col != col이면 1, 아니면 0)))으로 갱신합니다.
- total을 반환합니다.
- 메인 로직에서는 ans := helper(0, -1, 0)을 호출하고, ans가 inf가 아니면 ans를, 그렇지 않으면 -1을 반환합니다.
Python 구현 예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(houses, cost, n, target):
m = len(houses)
def helper(i, p_col, grp):
if i == m:
return 0 if grp == target else float('inf')
if houses[i] != 0:
return helper(i + 1, houses[i], grp + int(p_col != houses[i]))
total = float('inf')
for col in range(1, n + 1):
total = min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col != col)))
return total
ans = helper(0, -1, 0)
return ans if ans != float('inf') else -1
houses = [0,2,1,2,0]
cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]
n = 2
target = 3
print(solve(houses, cost, n, target))
입력
[0,2,1,2,0], [[1,10],[10,1],[10,1],[1,10],[5,1]], 2, 3
출력
11
성능 개선: 메모이제이션 활용
위 재귀 풀이는 같은 상태 (i, p_col, grp)를 여러 번 중복 계산할 수 있어 입력 크기가 커지면 실행 시간이 급격히 늘어납니다. functools.lru_cache 데코레이터로 메모이제이션을 적용하면 성능을 크게 향상시킬 수 있습니다. 상태의 개수는 O(m × n × target)이고 각 상태에서 최대 n가지 색을 시도하므로, 메모이제이션 적용 시 전체 시간 복잡도는 O(m × n² × target)이 됩니다.
from functools import lru_cache
def solve(houses, cost, n, target):
m = len(houses)
@lru_cache(maxsize=None)
def helper(i, p_col, grp):
if i == m:
return 0 if grp == target else float('inf')
if houses[i] != 0:
return helper(i + 1, houses[i], grp + int(p_col != houses[i]))
total = float('inf')
for col in range(1, n + 1):
total = min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col != col)))
return total
ans = helper(0, -1, 0)
return ans if ans != float('inf') else -1