99클럽 코테 스터디 14일차 TIL(그래프)

📎 문제링크

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

 

🤔 문제 이해 및 알고리즘 유형

알고리즘 유형

DFS

💻 틀린 코드

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        edge_list=[[] for _ in range(n)]
        visited=[False]*(n+1)
        def dfs(start,visited):
            if start==destination:
                return True
            visited[start]=True
            for e in edge_list[start]:
                if visited[e]==False:
                    dfs(e,visited)
            
        
        for edge in edges:
            edge_list[edge[0]].append(edge[1])
            edge_list[edge[1]].append(edge[0])
        if dfs(source,visited)==True:
            return True
        else:
            return False

👍 해결한 코드

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        edge_list = [[] for _ in range(n)]  
        
        for edge in edges:
            edge_list[edge[0]].append(edge[1])
            edge_list[edge[1]].append(edge[0])  
        
        visited = [False] * n
        
        def dfs(start):
            if start == destination:
                return True
            
            visited[start] = True
            for e in edge_list[start]:
                if not visited[e]:
                    if dfs(e):
                        return True
            return False
        
        return dfs(source)

✔ 생각해봐야 할 점

방법을 접근하는 것은 맞는데 DFS를 돌렸을 때 true 값이 나오면 return True를 해줘야 하는 것을 생각하지 못했다. 한번 더 생각하자.