Leetcode 797

문제 링크

문제 설명.

graph가 이중 배열 형태로 주어진다.
graph의 각 node i에서 다른 노드로 가는 endpoint는 graph[i]에 들어가있다.

시작 node 0에서 마지막 node까지의 모든 directed path를 배열 형태로 구하는 문제.

문제 풀이.

마지막 node의 경우는 간단히 len(graph)-1로 처리해주고, return 을 할 배열 res를 생성한다.
시작 node가 주어지기 때문에 deque Q에 [0]을 추가해주고, while문과 for 문을 사용해서 Q에서 뽑아낸 path의 마지막 node의 다음 node를 체크한다.
만약 다음 node가 마지막일 경우, res에 해당 path에 마지막 node를 추가해서 넣어주고, 아닐 경우 Q에 path에서 다음 node를 추가한 새로운 path를 추가해준다.

풀이 코드.

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        aim = len(graph)-1
        
        res = []
        Q = deque([[0]])
        while Q:
            path = Q.popleft()
            for i in graph[path[-1]]:
                if i == aim:
                    res.append(path+[aim])
                else:
                    Q.append(path+[i])
        
        return res