Today's Challenge

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

Find if Path Exists in Graph - LeetCode

내가 스스로 처음 푼 건 예제는 맞았는데 실제 제출하니 틀림 =_=
이미 방문한 vertex에 대해서는 제거하는 로직을 추가하면 쉽게 풀리는 듯.

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:        
        g = collections.defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        
        visited = [False] * n
        visited[source] = True
        qu = collections.deque([source])

        while qu:
            cur = qu.popleft()
            if cur == destination:
                return True
        
            for nn in g[cur]:
                if not visited[nn]:
                    visited[nn] = True
                    qu.append(nn)
        
        return False