[스파르타] 99클럽 2기 코테스터디 14일차 TIL / leet 797

LeetCode: 797. All Paths From Source to Target (링크)

 

input 값이 2차원 배열로 주어져서 어떻게 해야 했는데 다른 분의 풀이를 참고해보니 path + [end] 로 매번 더할 수 있는 걸 알게 되었다. 예를 들어 path = [[0, 1], [0, 2]], end = 3 이라면 path + end = [[0, 1, 3], [0, 2, 3]] 이런 식으로 구할 수 있다. 그래서 queue에 시작점인 0을 넣어주고 for문을 돌면서 해당 인덱스와 연결된 요소들도 마지막 인덱스가 아니라면 queue에 새로 넣어준다. 이걸 while문으로 queue값이 전부 없어질 때까지 돌면 연결된 모든 경로를 구할 수 있게 된다.

 

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        end = len(graph) - 1
        queue = deque([[0]])
        ans = []

        while queue:
            path = queue.popleft()
            for i in graph[path[-1]]:
                if i == end:
                    ans.append(path+[end])
                else:
                    queue.append(path+[i])
        return ans

오늘 미들러 풀이 끝!

---

참고한 블로그: https://velog.io/@dombe/Leetcode-797

Leetcode 797