797. All Paths From Source to Target

All Paths From Source to Target - LeetCode

그래프의 edge 정보가 주어진다.

0번 노드 ~ N-1번 노드까지 가능한 모든 경로를 구해 반환하는 문제다.

 

1. DFS

from typing import *


class Solution:
    def allPathsSourceTarget(self, input_list: List[List[int]]) -> List[List[int]]:
        graph = {}
        length = len(input_list)

        for i in range(length):
            graph[i] = set(input_list[i])
        answer = []

        def dfs(cur, seq):
            if cur == length - 1:
                answer.append(seq[::])

            else:
                for adj in graph[cur]:
                    seq.append(adj)
                    dfs(adj, seq)
                    seq.pop()

        dfs(0, [0])
        return answer

그래프를 잘 그려주고 DFS로 탐색하면 된다.

 

나는 보통 그래프를 그릴 때 dict과 set을 사용한다. 입력이 너무나도 빡빡할 때는 set에 넣는 행위 자체가 오버헤드가 되는 경우도 있지만 leetcode문제에선 아직까지 그런 경우는 만나지 못했다.

 

마지막에 반환할 때 seq [::]을 해서 복사한 배열 값을 넣어주는 게 포인트라면 포인트. 이거 은근 본방에서 못 찾아서 헤매는 경우가 있다.