[백준: Python] 17404 - RGB거리 2

[문제]

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

 

RGB 거리와 동일한 문제입니다. 다만 제약 조건으로 1번 집의 색과 n번 집의 색상이 서로 달라야 한다는 조건이 추가되었습니다.

 

해당 문제의 기본 규칙은 서로 인접한 집의 색상이 서로 달라야 한다는 것입니다.

 

기존 RGB 거리에서의 풀이는 현재 주어진 색상으로 칠한다고 가정했을 때, 바로 직전의 집들 중 해당 색상을 제외한 비용 중, 최소를 선택해서 갱신하면 되는 것이었습니다.

 

하지만 첫 번째 집과 마지막 집의 색상이 서로 달라야 하므로 처음 색상을 고정하는 추가적인 절차가 필요합니다. 해당 과정은 풀이에서 상세하게 다루겠습니다.

---

[초기화]

    def __init__(self):
        self.n = int(input())
        self.houses = [list(map(int, input().split())) for _ in range(self.n)]
        self.answer = math.inf

 

값을 최대로 초기화합니다. 문제 제약 조건에 따라 1,000(집의 최대 수) x 1,000(최대 비용) + 1(엣지 케이스 고려)도 가능합니다.

---

[풀이]

    def solve(self):
        for color in range(3):  # 각 색상에 대해
            cost = copy.deepcopy(self.houses)
            cost[0] = [math.inf] * 3  # 1번째 집 초기화
            cost[0][color] = self.houses[0][color]  # 색상별 집 고정 -> 선택된 값을 제외하고 큰 값을 가지므로 선택 불가

            for i in range(1, self.n):
                cost[i][0] += min(cost[i - 1][1], cost[i - 1][2])  # R
                cost[i][1] += min(cost[i - 1][0], cost[i - 1][2])  # G
                cost[i][2] += min(cost[i - 1][0], cost[i - 1][1])  # B
            cost[-1][color] = math.inf  # 첫 집과 마지막 집의 색상은 달라야하므로 처음에 선택된 집이 마지막에 선택되지 않도록 함
            self.answer = min(self.answer, min(cost[-1]))

        print(self.answer)

 

입력은 각 색상은 RGB 순으로 0, 1, 2의 인덱스를 가집니다. 이 순서들을 차례대로 돌아가며 어떤 색상으로 시작했을 때, 최솟값을 만들 수 있는지 계산합니다.

 

1. 비용 계산을 위해 비용 정보를 복사합니다. 해당 입력은 2차원 리스트로 받았기 때문에 깊은 복사를 수행합니다.
   • 얕은 복사를 수행할 경우 최상위 요소만 복사되기 때문에 내부 리스트들은 그대로 원본 리스트의 주소를 가리키는 문제가 발생하게 됩니다.
2. 색상 고정을 위해 첫 번째 요소의 비용을 최댓값으로 초기화합니다.
   • 초기화 후, 각 색상 순서에 맞춰 해당 값만 원래 값으로 돌려줍니다.
3. 두 번째 집부터 n-1까지 탐색하며 이전 집의 색상을 비교해서 색상별 최솟값을 만들어 냅니다.
   • 처음 R을 기준으로 탐색을 한다고 가정하겠습니다.
   • 첫 번째 집의 비용은 [x, inf, inf]입니다.
   • 다음 집부터 인접한 집의 색상을 서로 다르게 하기 위해 이전 집을 기준으로 각 색상을 제외한 색상들 중 최소를 선택해 합산합니다.
   • 위 처리에 따라 다음부터 칠해지는 R의 비용은 inf로 고정되게 됩니다.
     • inf라 최솟값으로 선택할 수 없음
   • 모든 값이 합산되면 마지막의 R의 값을 inf로 변경합니다.
     • 결과적으로 n = 3일 때 다음과 같은 형태가 만들어집니다.
       [x1, inf. inf]
       [inf, x2. x3]
       [inf, x4. x5]
4. 이후 마지막에 합산된 값들 중 최소 값을 선택해 현재 최적값과 비교해 값을 갱신합니다.
• 마찬가지로 R의 값은 inf로 최솟값으로 선택할 수 없습니다.
• 이렇게 되면 첫 번째 집의 R은 색상을 고정했기에 inf가 아닌 비용을 가지지만 이후 R의 비용은 inf이기 때문에 선택 대상에서 제외됩니다.
• 그렇기 때문에 첫 번째 집과 마지막 집의 색상이 서로 달라야 한다는 제약을 만족함과 동시에 인접한 집의 색상을 서로 다르게 칠할 수 있게 됩니다.
5. 위와 같은 절차를 색상별로 돌아가며 어떤 값으로 고정했을 때, 최적의 값을 만들어 낼 수 있는지 찾아냅니다.

---

[전체 코드]

import copy
import math


class Main:
    def __init__(self):
        self.n = int(input())
        self.houses = [list(map(int, input().split())) for _ in range(self.n)]
        self.answer = math.inf
        
    def solve(self):
        for color in range(3):  # 각 색상에 대해
            cost = copy.deepcopy(self.houses)
            cost[0] = [math.inf] * 3  # 1번째 집 초기화
            cost[0][color] = self.houses[0][color]  # 색상별 집 고정 -> 선택된 값을 제외하고 큰 값을 가지므로 선택 불가

            for i in range(1, self.n):
                cost[i][0] += min(cost[i - 1][1], cost[i - 1][2])  # R
                cost[i][1] += min(cost[i - 1][0], cost[i - 1][2])  # G
                cost[i][2] += min(cost[i - 1][0], cost[i - 1][1])  # B
            cost[-1][color] = math.inf  # 첫 집과 마지막 집의 색상은 달라야하므로 처음에 선택된 집이 마지막에 선택되지 않도록 함
            self.answer = min(self.answer, min(cost[-1]))

        print(self.answer)


problem = Main()
problem.solve()

---