[LeetCode] 756. Pyramid Transition Matrix

https://leetcode.com/problems/pyramid-transition-matrix/?envType=daily-question&envId=2025-12-29

LeetCode - Pyramid Transition Matrix

문제 유형: 구현, 백트래킹, 비트마스킹, dfs

문제 난이도: Medium

 

문제

You are stacking blocks to form a pyramid. Each block has a color, which is represented by a single letter. Each row of blocks contains one less block than the row beneath it and is centered on top.

To make the pyramid aesthetically pleasing, there are only specific triangular patterns that are allowed. A triangular pattern consists of a single block stacked on top of two blocks. The patterns are given as a list of three-letter strings allowed, where the first two characters of a pattern represent the left and right bottom blocks respectively, and the third character is the top block.

• For example, "ABC" represents a triangular pattern with a 'C' block stacked on top of an 'A' (left) and 'B' (right) block. Note that this is different from "BAC" where 'B' is on the left bottom and 'A' is on the right bottom.

You start with a bottom row of blocks bottom, given as a single string, that you must use as the base of the pyramid.

Given bottom and allowed, return true if you can build the pyramid all the way to the top such that every triangular pattern in the pyramid is in allowed, or false otherwise.

 

풀이

두 개의 문자 pair -> A ~ F에 대해 가능한 경우, 해당 대응 비트 켬 (1 << char)의 꼴로 한다.

즉, allows에서 삼각형 매핑 테이블을 6 * 6의 크기의 정수 테이블로 변환할 수 있다.

 

그리고, 부르트포스로 현재 문자열의 위칸에 올 수 있는 모든 경우의 수들을 구한 다음, 백트래킹을 시도한다.

중복 계산 방지를 위해, 실패한 적 있다면, unordered_set에 저장한다.

unordered_set에도 base6으로 인코딩한다.

 

자세한 구현은 아래를 참조한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
class Solution {
public:
    int T[6][6];
    unordered_set<int> bad;
    int encode(vector<int> &v) {
        int x = 0;
        for(int n : v) {
            x = x * 6 + n;
        }
        return x;
    }
    bool dfs(vector<int> &bot) {
        if(bot.size() == 1) return true;

        vector<vector<int>> cand;
        vector<int> curr;
        generate(bot, 0, curr, cand);

        if(cand.empty()) {
            return false;
        }
        for(auto &c : cand) {
            int key = encode(c);
            if(bad.count(key)) continue;
            if(dfs(c)) return true;
        }

        bad.insert(encode(bot));
        return false;
    }
    void generate(vector<int> &bot, int idx, vector<int> &curr, vector<vector<int>>& cand) {
        if(idx == bot.size()-1) {
            cand.push_back(curr);
            return;
        }

        int left = bot[idx];
        int right = bot[idx+1];
        int mask = T[left][right];
        for(int c = 0; c < 6; c++) {
            if(mask & (1 << c)) {
                curr.push_back(c);
                generate(bot, idx+1, curr, cand);
                curr.pop_back();
            }
        }
    }
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for(const auto &a : allowed) {
            T[a[0]-'A'][a[1]-'A'] |= 1 << a[2] - 'A';
        } 
        vector<int> bot;
        for(char ch : bottom) {
            bot.push_back(ch - 'A');
        }
        return dfs(bot);
    }
};