797. All Paths From Source to Target

797. All Paths From Source to Target

 

이 문제는 DAG(Directed Acyclic Graph, 방향 비순환 그래프)에서 시작 노드(0)에서 목표 노드(n−1)로 가는 모든 경로를 찾는 것입니다. 이 과정은 DFS(깊이 우선 탐색)를 이용하여 해결할 수 있습니다. 아래는 코드의 주요 흐름에 대한 한글 설명입니다.

---

1. DFS 함수 정의:
   • dfs 함수는 현재 노드(node)와 현재까지 탐색한 경로(path)를 인자로 받습니다.
   • 만약 현재 노드가 목표 노드(n−1)라면, 지금까지의 경로를 결과 리스트(result)에 추가합니다.
2. 재귀와 백트래킹:
   • 현재 노드의 모든 이웃 노드(neighbor)를 탐색합니다.
   • 이웃 노드를 경로에 추가한 뒤, 재귀적으로 dfs를 호출합니다.
   • 재귀 호출이 끝난 후에는 백트래킹(path에서 방금 추가한 노드 제거)을 통해 이전 상태로 돌아갑니다.
3. 결과 저장:
   • 모든 경로는 result 리스트에 저장됩니다.
   • 결과적으로, 모든 가능한 경로가 result에 포함됩니다.
4. 초기화:
   • 탐색은 노드 0에서 시작하며 초기 경로는 [0]으로 설정합니다.

왜 []을 가지는 곳이 목표 노드인가?

• 문제 조건:
  • 그래프는 방향 비순환 그래프(DAG)이며,
  • 노드 번호는 0부터 n−1 까지 순서대로 정해져 있습니다.
• 각 노드에는 방문할 수 있는 다음 노드의 목록이 주어집니다.
• []의 의미:
  • 노드가 []를 가진다는 것은, 더 이상 방문할 수 있는 노드가 없다는 것을 의미합니다.
  • 즉, 해당 노드는 "끝"이라고 볼 수 있으며, 이 노드가 목표 노드입니다.

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def dfs(target_node, path):
            # target_node: 타켓 노드 (현재 노드)
            # path: 현재까지 탐색한 경로
            
            # If we reach the target node, append the current path to the result
            if target_node == len(graph) - 1:
                result.append(path[:])
                return

            # Explore all neighbors of the current node
            for neighbor in graph[target_node]:
                path.append(neighbor)  # Add neighbor to the path, 경로 추가
                dfs(neighbor, path)   # Recursively explore the neighbor, 검색
                path.pop()            # Backtrack by removing the neighbor, 경로 삭제

        result = []
        dfs(0, [0])  # Start DFS from node 0 with the initial path [0]
        return result

# Example 1
graph1 = [[1, 2], [3], [3], []]
print(allPathsSourceTarget(graph1))
# Output: [[0, 1, 3], [0, 2, 3]]

# Example 2
graph2 = [[4, 3, 1], [3, 2, 4], [3], [4], []]
print(allPathsSourceTarget(graph2))
# Output: [[0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4], [0, 1, 4]]