[LeetCode] 1971. Find if Path Exists in Graph

https://leetcode.com/problems/find-if-path-exists-in-graph

Find if Path Exists in Graph - LeetCode

접근

• BFS 또는 DFS 로 탐색하는 문제
• graph, queue 를 활용해서 풀어야 합니다.
• 방문 여부 리스트를 통해 탐색 양을 최소화해야 합니다.

---

솔루션(DFS)

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = [[] for _ in range(n)]
        visited = [False for _ in range(n)]

        # initialize graph
        for index, value in enumerate(edges):
            graph[value[0]].append(value[1])
            graph[value[1]].append(value[0])

        # set cursor edge to source
        cursor_edge = source
        visited[cursor_edge] = True

        queue = [cursor_edge]

        while queue:
            cursor_edge = queue[0]
            # pop cursor_edge
            queue.pop(0)

            # if it get destination
            if cursor_edge == destination:
                return True
            
            # search child edge which can be cursor_edge
            for index, value in enumerate(graph[cursor_edge]):
                if visited[value] == False:
                    visited[value] = True
                    queue.append(value)
    
        return False