LeetCode - 1971. Find if Path Exists in Graph

[LeetCode] 1971. Find if Path Exists in Graph

LeetCode 1971번 문제를 풀어보았다.. Link

Problem

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Intuition

Graph (Tree)를 구현한 다음 그래프 사이를 지나다니면서 유효한 길이 있는지 확인하면 풀 수 있을 것으로 보인다.

그래프를 탐색하는 방법으로는 DFS나 BFS가 있으니까 이 알고리즘들을 사용해야겠다.

Approach

BFS를 사용한다고 했을 때..

1. 방문할 노드를 저장하기 위한 대기열인 queue를 초기화한다.
2. 이미 방문한 노드를 표시할 Bool형 배열인 seen을 생성하고, Graph를 표현할 Dictionary를 만든다.
3. Queue의 시작 노드인 source를 추가하고 seen에 방문한 것으로 업데이트한다.
4. Queue에 노드가 있으면 가져온 다음 Destination인지 아닌지 판별한다. Destination이면 True를 반환하고 아니면 5단계로 이동한다.
5. 아직 방문하지 않은 이웃노드는 Queue에 추가하고 4단계를 반복한다.
6. Queue가 결국 비워지게 되면 False를 반환한다.

위에는 사실 LeetCode의 Official Solution에 적힌 접근방법이고, 내가 쓴거는 아래와 같음

1. source와 연결되어있는 vertex들을 확인
2. 연결되어 있는 vertex가 destination이 아닌지 확인
3. destination이 아니면 자신과 연결되어 있는 다른 vertex 확인
4. 그게 destination인지 아닌지 판별
5. 위 과정 반복

확실히.. 나처럼 쓰면 어떤 자료구조를 쓰는지, 어떤 변수를 쓰는지, 무엇이 반복되는지, 어떤걸 판별하는지 알아보기 힘들다.

LeetCode의 Solution처럼 작성하는 방법을 익혀야겠다.

Complexity

• Time complexity:

  시간복잡도는 엣지(연결부)의 개수와 노드(vertex)의 개수에 따라 정해진다. 엣지 정보로 그래프를 형성하는데 O(e), 그리고 각 노드를 Queue에 넣어 탐색하는데 O(n)이 필요함으로 최종 시간복잡도는 O(e + n)이다.

  (이때 e는 edge의 개수, n은 노드의 개수)

• Space complexity: 딕셔너리 형성에 필요한 O(e), 특정 노드를 이미 탐색했는지 안했는지 기록하는 Bool형 배열 생성에 O(n)으로 시간복잡도와 똑같은 O(e+n)

My Code

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        """
        1. source와 연결되있는 node에 접근
        2. node의 값이 destination과 같은지 확인
        3. 현 node를 source로 하고 여기에 연결되있는 node에 접근
        4. node의 값이 destination과 같은지 확인 반복
        """
        graph = {}
        seen = [False] * n
        for i in range(n):
            graph[i] = []

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        queue = [source]
        while queue:
            current = queue.pop(0)
            if current == destination:
                return True
            
            for i in graph[current]:
                if not seen[i]:
                    seen[i] = True
                    queue.append(i)
        return False