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

https://leetcode.com/problems/painting-a-grid-with-three-different-colors/description/?envType=daily-question&envId=2025-05-18

Leetcode - Painting a Grid With Three Different Colors

문제 유형: 타일링, 다이나믹 프로그래밍, dfs

문제 난이도: Hard

 

문제

You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 10^9 + 7.

 

두 개의 정수 m, n이 주어진다. m x n의 행렬에서 모든 셀은 흰색이다. 빨간색, 초록색, 또는 파란색으로 색칠해야 한다.

단, 인접한 셀끼리 같은 색을 칠하지 못한다. 

셀들을 칠하는 경우의 수를 구하시오.

 

값이 커질 수 있으니, 10억+7로 나누시오.

 

풀이

dp[열번호][상태]로 한다.

'상태'란, 한 열의 상태를 말한다.

[0, 1, 0]이면, 빨간색, 초록색, 빨간색 순서로 칠했다는 의미이다.

상태는 dfs(재귀)로 3^5가지 중 유효한 조합들만을 골라낼 수 있다.

이렇게 모든 상태들을 생성하여 2D배열로 저장하면, 각각은 i번째 상태로 불릴 수 있다.

전이가능성에 대해 빠르게 접근하기 위해, adj[i][j] = i에서 j로 전이가능(i와 j는 인접한 상태여도 괜찮음)으로 정의시킬 수 있다.

 

 

그 뒤, dp[1][모든 유효한 state번호] = 1로 초기화한다.

그 뒤부터, dp[2] ~ dp[n]에서는 각각, 현재상태와 이전상태 조합을 모두 확인하면서, 가능하다면 경우의 수를 누적해서 전이경우를 고려해준다.

 

그 뒤, dp[n]의 모든 총합을 리턴하면 된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
using ll = long long;
const ll MOD = 1e9+7;
class Solution {
    int m, n;
    vector<vector<int>> states;
public:
    bool valid(int a, int b) {
        for(int i = 0; i < m; i++) {
            if(states[a][i] == states[b][i]) return false;
        }
        return true;
    }
    void make_states(vector<int> &temp) {
        if(temp.size() == m) {
            states.emplace_back(temp.begin(), temp.end());
            return;
        }
        for(int i = 0; i < 3; i++) {
            if(temp.empty() || temp.back() != i) {
                temp.emplace_back(i);
                make_states(temp);
                temp.pop_back();
            }
        }
    }
    int colorTheGrid(int m, int n) {
        this -> m = m;
        this -> n = n;

        vector<int> temp = {};
        make_states(temp);
        int numStates = states.size();   
        vector<vector<bool>> adj(numStates, vector<bool>(numStates, 0));
        for(int i = 0; i < numStates; i++) {
            for(int j = i+1; j < numStates; j++) {
                if(valid(i, j)) {
                    adj[i][j] = true;
                    adj[j][i] = true;
                }
            }
        }
        vector<vector<ll>> dp(n+1, vector<ll>(numStates, 0));
        for(int state = 0; state < numStates; state++) {
            dp[1][state] = 1;
        }
        for(int i = 2; i <= n; i++) {
            for(int curState = 0; curState < numStates; curState++) {
                for(int lastState = 0; lastState < numStates; lastState++) {
                    if(adj[curState][lastState]) {
                        dp[i][curState] = (dp[i][curState] + dp[i-1][lastState]) % MOD;
                    }
                } 
            }
        }

        ll ans = 0;
        for(int i = 0; i < numStates; i++) {
            ans = (ans + dp[n][i]) % MOD;
        }
        return ans;
    }
};

 

Go

const MOD int64 = 1_000_000_007

type MatState struct {
    states [][]int
    adj [][]bool
    numStates int
    numColors int
    m int
    n int
}

func NewMS(m, n int) *MatState {
    return &MatState{m:m, n:n, numColors:3} 
}

func (MS *MatState) Generate() {
    temp := make([]int, 0)
    MS.dfs(temp)
    MS.numStates = len(MS.states)

    MS.adj = make([][]bool, MS.numStates)
    for i := 0; i < MS.numStates; i++ {
        MS.adj[i] = make([]bool, MS.numStates)
    }

    for i := 0; i < MS.numStates; i++ {
        for j := 0; j < MS.numStates; j++ {
            flag := true
            for k := 0; k < MS.m; k++ {
                if MS.states[i][k] == MS.states[j][k] {
                    flag = false
                    break
                }
            }
            if flag {
                MS.adj[i][j] = true
                MS.adj[j][i] = true
            }
        }
    }
}

func (MS *MatState) dfs(temp []int) {
    if len(temp) == MS.m {
        state := make([]int, MS.m)
        copy(state, temp)
        MS.states = append(MS.states, state)
        return
    }

    for i := 0; i < MS.numColors; i++ {
        if len(temp) == 0 || temp[len(temp)-1] != i {
            temp = append(temp, i)
            MS.dfs(temp)
            temp = temp[0:len(temp)-1]
        }
    }
}

func colorTheGrid(m int, n int) int {
    MS := NewMS(m, n) 
    MS.Generate()

    dp := make([][]int64, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int64, MS.numStates)
    }

    for state := 0; state < MS.numStates; state++ {
        dp[1][state] = 1
    }

    for i := 2; i <= n; i++ {
        for curState := 0; curState < MS.numStates; curState++ {
            for lastState := 0; lastState < MS.numStates; lastState++ {
                if MS.adj[curState][lastState] {
                    dp[i][curState] = (dp[i][curState] + dp[i-1][lastState]) % MOD
                }
            }
        }
    }

    ans := int64(0)
    for i := 0; i < MS.numStates; i++ {
        ans = (ans + dp[n][i]) % MOD
    }

    return int(ans)
}