[Leetcode] 1931. Painting a Grid With Three Different Colors

문제 설명

m x n 크기의 격자가 있다.
각 칸은 반드시 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다.

단, 서로 인접한 칸은 같은 색으로 칠할 수 없다.
여기서 인접하다는 것은 상하좌우 방향을 의미한다.

이 조건을 만족하도록 모든 셀을 칠하는 방법의 수를 구하라.
답이 매우 클 수 있으므로 1,000,000,007 (10⁹+7) 로 나눈 나머지를 반환하라.

 

예시

• 예제 1
  입력: m = 1, n = 1
  출력: 3
  설명: R, G, B 중 하나를 선택할 수 있다 → 3가지

• 예제 2
  입력: m = 1, n = 2
  출력: 6
  설명: 첫 칸을 3가지 중 하나로 칠하고, 다음 칸은 나머지 2가지 중 하나 선택 → 3×2 = 6

• 예제 3
  입력: m = 5, n = 5
  출력: 580986
  설명: 조건을 만족하는 방법 수는 매우 많다. 효율적인 계산이 필요

조건(제약사항)

• 1 ≤ m ≤ 5
• 1 ≤ n ≤ 1000
• 시간 초과를 방지하기 위해 효율적인 알고리즘이 필수다.

풀이전략

동적 계획법(Dynamic Programming) + 상태 압축(State Compression)

행 기반 상태 정의

• m이 작기 때문에 열 방향으로 진행하면서 각 열의 행 색상 조합을 상태로 관리할 수 있다.
• 각 열은 m개의 셀이 있으므로, 가능한 색 조합(단, 인접한 셀끼리는 다른 색이어야 함)을 미리 생성한다.

풀이를 그림으로 요약

유효 상태 전이 저장

• 열 i와 열 i+1이 전이 가능한 조건: 같은 행 위치의 색이 다르면 된다.
• 이 조건을 만족하는 상태 쌍만을 이용하여 DP를 구성한다.

DP 정의

• dp[col][state]: col번째 열까지 칠했고, 그 열의 색 조합이 state일 때 가능한 칠하는 방법 수
• 초기값은 모든 첫 열의 유효한 상태에 대해 dp[0][state] = 1

점화식

다음 열에서 next_state가 올 수 있는 경우는 curr_state와 next_state는 전이 가능할 때:

$dp[col+1][next_state] += dp[col][curr_state]$

답은 마지막 열(n-1)의 모든 상태를 더한 값이 정답이 된다.

시간복잡도

• 상태 수는 최대 3^m (m ≤ 5 → 최대 243)
• 열 수 n이 최대 1000이므로 전체 연산은 약 n * 243 * 243 ≈ 59M 이하 → 가능

풀이 코드

from collections import deque

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        mod = pow(10, 9) + 7
        idx, rgb = 0, ['r', 'g', 'b']
        grid_map = {}
        q = deque(rgb)

        while q:
            s = q.popleft()
            if len(s) == m:
                if self.check(s, m):
                    grid_map[idx] = s
                    idx += 1
                continue
            for color in rgb:
                q.append(s + color)
        
        L = len(grid_map)
        possible_map = [[False for i in range(L)] for j in range(L)]

        for i in range(L):
            for j in range(i + 1, L):
                if self.check_str(grid_map[i], grid_map[j]):
                    possible_map[i][j] = True
                    possible_map[j][i] = True

        dp = [[0 for i in range(L)] for j in range(n)]
        for i in range(L):
            dp[0][i] = 1

        for k in range(1, n):
            for i in range(L):
                for j in range(L):
                    if possible_map[i][j]:
                        dp[k][i] += dp[k-1][j] % mod
        
        return sum(dp[n - 1]) % mod
        
    def check(self, s:str, m:int):
        for i in range(m - 1):
            if s[i] == s[i + 1]:
                return False
        return True

    def check_str(self, s1:str, s2:str):
        if len(s1) != len(s2):
            return False
        for ch1, ch2 in zip(s1, s2):
            if ch1 == ch2:
                return False
        return True

 

요약(핵심)

• 색상 조건을 만족하는 모든 행 조합을 상태(state)로 저장한다.
• 각 열마다 이전 열에서 전이 가능한 상태들만 이용하여 동적 계획법을 구성한다.
• 전이 조건은 같은 행의 같은 위치 색이 다른지 여부이다.
• 모든 열에 대해 가능한 상태를 누적하며 진행하면 최종 답을 얻을 수 있다.

이 문제는 상태 공간 축소와 DP를 조합한 전형적인 그리드 탐색 최적화 문제이다.
입력의 폭은 넓지만 높이가 작을 때, 상태 압축(State Compression)을 어떻게 활용할 수 있는지 보여주는 좋은 예이다.