Graphs (싸이클 탐지): 1971. Find if Path Exists in Graph

1971. Find if Path Exists in Graph

 

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        # 양방향 그래프를 인접 리스트로 생성
        adj = {i: [] for i in range(n)}
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)

        # 방문한 노드를 추적하기 위한 집합
        visit = set()

        # DFS 함수 정의
        def dfs(i):
            if i == destination:  # 목적지에 도달하면 True 반환
                return True
            
            visit.add(i)  # 현재 노드를 방문 처리
            for j in adj[i]:
                if j not in visit:  # 방문하지 않은 노드만 탐색
                    if dfs(j):  # 목적지로 가는 경로를 찾으면 True 반환
                        return True
            return False  # 경로를 찾지 못하면 False 반환
        
        # DFS 호출 시작
        return dfs(source)