99클럽 코테 스터디 16일차 TIL Leetcode Find if Path Exists in Graph

Leetcode Find if Path Exists in Graph

시작점과 끝점이 주어진 간단한 그래프 문제

처음 나는 dfs 문제로 풀었다가 메모리나 속도가 다른 풀이들에 비해 떨어지는 것을 확인하고, bfs로 코드를 바꿨다.

그러고나니 메모리는 상위 0.5%정도 됐다. (근데 웃긴건 몇번 돌려보니 결과가 상당히 랜덤이었다..)

나의 코드

from collections import deque
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph=[set() for _ in range(n)]
        visited=[False for _ in range(n)]
        for s,e in edges:
            graph[s].add(e)
            graph[e].add(s)
        queue=deque()
        queue.append(source)
        while queue:
            p=queue.popleft()
            if p==destination:
                return True
            for q in graph[p]:
                if not visited[q]:
                    visited[q]=True
                    queue.append(q)
        return False