[LeetCode] 1971. Find if Path Exists in Graph (Daily Question)

문제

---

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.

 

노드 개수, 노드의 연결, 출발지, 목적지가 주어졌을 때 출발지에서 목적지까지 갈 수 있는지 판단하는 문제이다. 

 

Example 1:
Input: n = 3,edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2: - 0 → 1 → 2 - 0 → 2

Example 2:
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

 

풀이

---

아이디어

출발지 노드에서 시작해서 목적지 노드에 도착할 때까지 BFS로 다음 노드들을 탐색한다.

코드

class Solution:
    answer = False

    # 탐색 함수
    def search(self, nodes):
        # 탐색할 노드가 없으면 종료
        if not nodes: return
        
        # 노드 방문 기록
        for node in nodes:
            self.visited[node] = True

        next_nodes = set([])
        for node in nodes:
            # 끝 단 노드는 스킵
            if not self.connections[node]: continue
            for connected_node in self.connections[node]:
                # 목적지에 도달했다면 종료
                if connected_node == self.destination: 
                    self.answer = True
                    return
                if not self.visited[connected_node]: next_nodes.add(connected_node)

        self.search(list(next_nodes))

    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        # 특정 노드에 대해 연결된 노드들을 담는 딕셔너리 생성
        # ex) {0: [1, 2, 3]}
        connections = {}
        for edge in edges:
            node1, node2 = edge
            if node1 not in connections: connections[node1] = []
            if node2 not in connections: connections[node2] = []

            connections[node1].append(node2)
            connections[node2].append(node1)

        self.visited = [False for _ in range(n)]
        self.destination = destination
        self.connections = connections

        # 출발지와 목적지가 같다면 True 반환
        if source == destination: return True
        self.search([source])

        return self.answer

노드들 간의 연결이 리스트로 주어지긴 하지만, 그대로 사용할 수 없지 않을까해서 딕셔너리로 가공했다.

---

 

후기

---

난이도

처음에 목적지까지 갈 수 있는 경로의 개수를 찾는 문제로 착각해서 시간을 좀 허비했다.

 

탐색 알고리즘을 알고 있다면 어렵지 않게 풀 수 있는 문제였던 것 같다.

다만 연결된 노드가 없는 경우, 출발지와 목적지가 같은 경우를 생각하고,

리스트나 각종 변수를 전역 혹은 지역으로 적절히 사용하는데 있어서 헷갈릴 수는 있을 것이다.