1. What I learned
Insert two different elements into a list
To insert different elements into a list, write as follows.
stack = [(e,[LIST])]
#don't forget to write ().
2. How I sloved
I used DFS to get all the routes from 0 to node n-1. Start was always zero and end was n-1. Each node had several routes to other nodes. So I kept storing the previous route on the stack. Because the output was a double-list, when I reached the end node I added a route that was a list to the output list.
3. Code
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
def findPath(start):
route= []
stack = [(start,[start])]
while stack:
node,route = stack.pop()
if node==len(graph)-1:
routes.append(route)
for e in graph[node]:
stack.append((e,route+[e]))
routes = []
findPath(0)
return routes
4. Result
Runtime : 96 ms(92.80%), Memory usage : 15.3 MB(25.16%)
(Runtime can be different by a system even if it is a same code.)