99클럽 코테 스터디 14일차 TIL + Backtracking/Depth-First Search/Breadth-First Search Graph : all-paths-from-source-to-target

문제

링크텍스트

풀이

# from typing import Optional
from typing import List

from collections import deque
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        q = deque()
        q.append([0,[0]])
        a = []
        while q:
            qi = q.popleft()
            for j in graph[qi[0]]:
                q.append([j,qi[1]+[j]])
                if j == n-1:
                    a.append(qi[1]+[j])
        return a
        
for i in range(2):
    print(f'test case: {i}')
    if i == 0:
        graph = [[1,2],[3],[3],[]]
        Output = [[0,1,3],[0,2,3]]
    if i == 1:
        graph = [[4,3,1],[3,2,4],[3],[4],[]]
        Output = [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

    sol = Solution()
    a = sol.allPathsSourceTarget(graph)
    print(a)
    print(Output)

• BFS로 풀었습니다.
• q에 현재 node, x와 현재 node까지의 path, p를 넣습니다.
• q가 빌때까지
  • pop()하여 x와 p를 구합니다.
  • graph[x]로 x가 가리키는 node를 구하여, 현노드 x와 path, p를 update합니다.
  • update된 x와 p를 q에 다시 넣습니다.
  • 만약, update된 x가 마지막 node이면 a에 해당 path를 추가합니다.

결과