LeetCode : 756. Pyramid Transition Matrix

 

문제)

 

주어지는 문자열 allowed에서 앞에 두글자가 각각 왼쪽아래, 오른쪽아래 블록이다.

이때 allowed로 피라미드를 끝까지 만들 수 있는지에 대한 결과를 리턴해주면 되는 문제이다.

 

문제 난이도 : 중

 

소요시간 및 풀이)

DFS를 이용하여 풀었다.

 

처음 Map에 주어진 allowed에서 아래 두 블록의 글자와 그 위의 글자를 넣어준다.

 

처음 dfs에 진입했을 때 bottom에서 0번째 부터 시작하여 두글자씩 문자열을 가져와서 prefix에 저장.

그 후, Map에서 prefix로 데이터를 찾아서 다시 dfs를 호출한다. (아래 블럭의 위에 있는 블럭의 문자를 저장.)

이 때, dfs를 호출할 때 매개변수로 (row, nextRow + c, i+1, Map) 넣어준다.

 

        if (nextRow.length() == row.length() - 1)
            return dfs(nextRow, "", 0, Map);

 

이런식으로 처음 bottom을 모두 순회하면 위 코드로 인해 다시 dfs가 호출된다.

nextRow가 비어있는 dfs 즉, 다음 번째 줄 순회를 시작하게 된다.

 

이 과정을 반복해서 row의 길이가 1이 되면 성공적으로 피라미드가 완성 된것이므로, true를 리턴해준다.

 

소요 시간 : 40분

 

정답 코드

class Solution 
{
private:
    bool dfs(const string& row, const string& nextRow, int i, unordered_map<string, vector<char>>& Map)
    {
        if (row.length() == 1)
            return true;

        if (nextRow.length() == row.length() - 1)
            return dfs(nextRow, "", 0, Map);

        const string& prefix = row.substr(i, 2);

        if (Map.find(prefix) != Map.end())
        {
            for (auto c : Map[prefix])
                if (dfs(row, nextRow + c, i + 1, Map))
                    return true;
        }
        return false;
    }

public:
    bool pyramidTransition(string bottom, vector<string>& allowed) 
    {
        unordered_map<string, vector<char>> Map;

        for (auto& a : allowed)
            Map[a.substr(0, 2)].push_back(a[2]);

        return dfs(bottom, "", 0, Map);
    }
};