1. 문제 소개

756. Pyramid Transition Matrix

2. 나의 풀이

dfs를 사용해 풀었는데, 다른 풀이를 보고 푼 것이라 헷갈린다.

class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        candidate = defaultdict(set)                         # (아래 2칸) -> (위에 올릴 수 있는 문자들) 매핑

        for u, v, w in allowed:                              # allowed의 각 문자열 "UVW"를 (U,V)->W로 해석
            candidate[u, v].add(w)                           # 동일 (U,V)에 대해 여러 W가 가능하므로 set에 저장
        
        def add_neighbor(node):
            res = ['']                                       # 다음 층 문자열 후보들을 누적 생성(초기에는 빈 문자열 1개)
            for i in range(1, len(node)):                    # 인접쌍 (node[i-1], node[i])를 순회
                uppers = candidate[(node[i-1], node[i])]     # 해당 인접쌍 위에 올릴 수 있는 문자 집합
                if uppers:                                   # 가능 문자가 존재하면
                    res = [r + u for u in uppers for r in res]
                                                             # 기존 후보 r들에 대해 u를 뒤에 붙여 후보 확장(데카르트 곱)
                else:                                        # 어떤 위치에서라도 가능한 문자가 없으면
                    return []                                # 해당 node에서 다음 층을 만들 수 없으므로 빈 리스트 반환
            return res                                       # 가능한 다음 층 문자열 후보들 반환

        visited = set()                                      # 실패가 확정된 층 문자열(node)을 메모(가지치기)

        def dfs(node):
            if len(node) == 1:                               # 꼭대기(길이 1)에 도달하면 성공
                return True
            if node in visited:                              # 이미 이 node에서 실패했음을 알면 재탐색 불필요
                return False

            for nxt in add_neighbor(node):                   # 가능한 다음 층 후보들을 모두 시도
                if dfs(nxt):                                 # 하나라도 성공하면
                    return True                               # 즉시 True 반환
            
            visited.add(node)                                # 모든 후보가 실패했으면 이 node는 실패 상태로 기록
            return False                                     # 실패 반환

        return dfs(bottom)                                   # 바닥층에서 DFS 시작

3. 다른 풀이

다른 풀이를 보고 풀어서 넘어간다.

4. 마무리

dfs를 좀 더 공부해야한다.