[99클럽 코테 스터디 14일차 TIL] LeetCode | 797. All Paths From Source to Target

14일차 DFS

Problem

https://leetcode.com/problems/all-paths-from-source-to-target/description/

Sol

0부터 n-1번 노드까지 갈 수 있는 모든 경로를 알려주는 문제(Source ➡️ Target)

---

✔ Answer

[DFS]
모든 경로를 탐색해야하기 때문에 stack과 회귀를 사용하는 DFS 방식으로 문제를 해결했습니다.

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def dfs(node, path):
            # 목표 노드(n-1)도착하면 경로를 결과 리스트에 추가
            if node == len(graph) - 1:
                result.append(path)
                return
            
            # 현재 노드에서 갈 수 있는 모든 노드를 순회
            for next_node in graph[node]:
                dfs(next_node, path + [next_node])

        result = []
        dfs(0, [0])  # 시작 노드, 경로 0번 [0]에서 시작
        return result

---

💬 이동시간에 짬을 내서 폰으로 문제를 풀어봤는데 의외로 집중도 잘되고 더 재밌게 풀었다. 주말에도 화이팅!