(25.03.25) 비트 마스크의 활용 : DP

DP 알고리즘은 메모이제이션과 이를 누적해서 DP 테이블에 저장하는 재귀 또는 반복을 채택하고 있다.

하지만, 어떤 경우에는 저장해야하는 경우의수가 너무 많아 메모리를 너무 많이 사용하거나, 또는 알고리즘 코드를 작성하는데 복잡도가 높아질 수 있다.

 

이때 이전의 모든 조합 구하는 방식인 "비트마스크"를 활용해서 비교하면서 진행할 수 있다.

---

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 109 + 7.

m*n 크기의 테이블에 3가지 색을 연속해서 배채시키지 않을 떄의 모든 경우의 수를 구하는 문제

class Solution {

    private final int MOD = 1000000007;

    public int colorTheGrid(int m, int n) {

        // 한 열에 만들 수 있는 모든 패턴 구하기
        List<Integer> patterns = new ArrayList<>();
        findPatterns(patterns, m, 0, 0 );

        // DP 테이블 생성
        int patternSize = patterns.size();
        int[][] dp = new int[n][patternSize];

        // 초기값 설정
        // 모든 패턴은 첫번째에 하나밖에 누적이 안되어있으므로
        Arrays.fill(dp[0], 1);

        // 1~n 열 까지 진행하면서 패턴끼리 조합 DP 저장
        for(int col = 1; col < n; col++) {
            for(int i = 0; i < patternSize; i++) {
                for(int j = 0; j < patternSize; j++) {
                    // i 번 패턴과 j번 패턴과 비교 : 좌우 인접하는지 비교
                    int patternA = patterns.get(i);
                    int patternB = patterns.get(j);

                    boolean isValid = true;
                    for(int p = 0; p < m; p++) {
                        if((patternA & 3) == (patternB & 3)) {
                            isValid = false;
                            break;
                        } else {
                            patternA >>= 2;
                            patternB >>= 2;
                        }
                    }

                    if(isValid) {
                        dp[col][i] = ( dp[col][i] + dp[col-1][j] ) % MOD;
                    }


                }
            }
        }

        // 마지막 DP 모든 값 다 더하기
        int answer = 0;
        for(int count : dp[n-1]) {
            answer = ( answer + count ) % MOD; 
        }
        
        return answer;
    }

    // 재귀하면서 3가지 색으로 만들수 있는 모든 조합 저장
    public void findPatterns(List<Integer> patterns, int m, int count, int pattern) {
        // m 개가 만들어지면 patterns 에 넣기
        if(m == count) {
            patterns.add(pattern);
            return;
        }

        // RGB 3개 각각 01 10 11 로 비트마스크로 진행 
        for(int color = 1; color <= 3; color++ ) {
            if( count == 0 || (pattern & 3) != color ) {
                findPatterns(patterns, m, count +1, (pattern << 2) | color);
            }
        }
    }


}

 

 

• findPatterns 메서드에서 만들수 있는 컬럼 크기(m)의 모든 패턴의 수를 만들고, 그 것을 가지고 열(n) 의 수만큼 그 패턴에서 조합을 해서 DP로 진행하는 플로우로 설정
  • 기존의 왼쪽에서 올 때, 위에서 올 때 dp 테이블을 실제 m*n 테이블과 똑같이 만들어서 계속 누적하는 형태를 사용하기엔 값이 너무 많이 커지고, 로직이 굉장히 복잡해짐
• (pattern & 3) != color
  • 비트AND 연산을 사용해서 3이라고 하면 비트로 나타낸 2진법 수에서 000011 이런 식의 3과 AND를 쓰기 때문에 → pattern의 만 뒤 두자리 숫자만 나올 수 있음
  • 마스킹을 통해서 R 01 = 1 , G 10 = 2, B 11 = 3 로 선정해서 RGB를 011011 로 나타내는 pattern을 계속 저장하는 형태이기 때문에 유용하게
    • 따라서 color와 비교가 가능
• (pattern << 2) | color)
  • 패턴을 오른쪽으로 2열 비트를 밀고, 해당 color 를 비트 OR 연산으로 해 그냥 입력
  • 비트를 밀때 해당 위치에 00 이 오기 때문에, 결국 color를 그 부분에 넣는다는 의미
• patternA >>= 2;
  • 비트 연산자도 =과 함께 사용해서 바로 덮어쓰기가 가능
  • 이 부분은 오른쪽으로 패턴을 밀어서 없애기 때문에 일종의 queue 처럼 쓸 수 있음

따라서, 굳이 String으로 Red, Green, Blue를 지정하지 않아도 비트 마스킹으로 빠르게 판단해서 진행이 가능

---

비트 마스킹은 이해하는데 조금 어려울 수 있지만, 실제 자료에 따라서 String으로 만든다거나, 또는 O(N) 시간 복잡도로 순회하면서 확인하는 작업을 굉장히 빠르게 할 수 있다.

실제로 DP 에도 메모이제이션의 메모리 한계가 많기 때문에, 모든 경우의 수를 빠르게 비트 마스킹으로 만드록 그 패턴을 적용시키는데 효율적으로 사용할 수 있을 것이라 생각한다.