[Graph] 797. All Paths From Source to Target

문제

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

All Paths From Source to Target - LeetCode

- 시작점부터 종점까지 이어지는 가능한 모든 경로 케이스 찾기

접근방법

1. index노드와 연결된 모든 노드의 정보가 담긴 이중 리스트가 주어진다.

• graph[0]: 0번 노드와 연결된 모든 노드 정보가 담긴 리스트 

2. 종점까지 모든 경로를 탐색하기 위해 DFS(depth-first-search) 재귀 호출 방식으로 접근.

• base case 정의
• base case에서 탈출 전에 원하는 정보를 만들어내기 
• dfs 함수 재귀적으로 호출해주기 (dfs 인수 명확하게 전달)

3. dfs함수는 시작노드와 경로정보를 인수로 받는다. 

• dfs( 0, [0] )   # dfs(node, path)  , 시작경로가 0이므로 path = [0]
• node에는 다음으로 탐색할 노드가 전달되고, path는 지금까지 경로를 저장한 리스트가 전달
• 해당 유형에서는 별도의 방문처리를 요구하지는 않으므로 생략 

4. 재귀호출 방식이므로 base case (탈출조건)을 반드시 명시.

(idea)
다음 dfs 호출 때 path 정보를 넘기기 위해  path + [ next_node ] 형태로 넘겨준다. 
- 이는 기존까지 경로와 다음 연결된 노드까지 합친 경로가 된다.

코드

        

          

            

            

            

          
          
PYTHON
          
        
      class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def dfs(node, path):
            # 현재 노드가 목표 노드(n - 1)에 도달하면 경로를 결과에 추가 후 return
            if node == len(graph) - 1: # base case 
                result.append(path)
                return
            # 다음 방문할 노드에 대해 DFS 수행
            for next_node in graph[node]:
                dfs(next_node, path + [next_node]) # node와 연결된 next_node로 dfs 순회호출
                
        result = []
        dfs(0, [0])  # 0번 노드에서 시작
        return result