(Python3) - LeetCode (Easy) : 1971. Find if Path Exists in Graph

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

BFS 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. 삽입삭제에 O(1)이 걸리는 deque를 사용하기 위해 변수 dq, 방문 여부 판단을 위한 check배열, 인접리스트 형태로 간선을 저장할 edges_map을 선언 후 적절히 초기화합니다.

 

2. 인접리스트 만들 때 양 방향 그래프인 점 유의하며 넣어줍니다.

📔 풀이과정

1. 시작점은 source이므로 dq에 source를 넣어주고 방문처리해줍니다.

 

2. dq가 비어 있는 동안 원소를 pop해 destination인지 비교하고 맞다면 도착가능하므로 True를 바로 반환합니다. 아니라면 인접리스트에 방문 가능한 다음 node를 찾아 dq에 append해줍니다.

📔 정답 출력 | 반환

탐색결과 destination에 도착하지 못했으므로 False를 반환합니다.

---

📕 Code

📔 Python3

from collections import deque

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        dq = deque()
        dq.append(source)
        check = [0]*n
        check[source] = 1
        edges_map = {i:[] for i in range(n)}
        for e in edges:
            edges_map[e[0]].append(e[1])
            edges_map[e[1]].append(e[0])

        while dq:
            node = dq.popleft()
            if node == destination:
                return True
            for e in edges_map[node]:
                if check[e] == 1:
                    continue
                check[e] = 1
                dq.append(e)

        return False

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.