[LeetCode] 1971. Find if Path Exists in Graph

 

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

Leetcode - Find if Path Exists in Graph

문제 유형 : 그래프, dfs / bfs

문제 난이도 : Easy

 

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.

 

무방향그래프가 n개의 정점으로 주어진다. 정점의 라벨은 0부터 n-1까지이다.

간선들은 edges[i] = [ui, vi]에서, u와 v가 연결되어있음을 알린다.

source에서 destination까지 경로가 있는지 판별하시오.

 

풀이

간단한 dfs/bfs 문제이다.

시작을 source에서 해서 dfs/bfs를 한 뒤, 끝내 destination에 방문하지 못하면 경로가 없는 것이다.

 

간선의 정보로 인접 행렬을 만들어서 해결할 수 있다.

 

코드

C++

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        if(n == 1 || source == destination) return true;
        vector<vector<int>> graph(n, vector<int>());
        for(const auto &edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        queue<int> q;
        vector<bool> visited(n, false);

        q.push(source);
        visited[source] = true;

        while(!q.empty()) {
            int curr = q.front();
            q.pop();

            for(const auto &next : graph[curr]) {
                if(next == destination) return true;
                if(!visited[next]) {
                    visited[next] = true;
                    q.push(next);
                }
            }
        }

        return false;
    }
};

 

Go

func validPath(n int, edges [][]int, source int, destination int) bool {
    if n == 1 || source == destination {
        return true
    }

    graph := make([][]int, n)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        graph[edge[1]] = append(graph[edge[1]], edge[0])
    }

    q := []int{source}
    visited := make([]bool, n)
    visited[source] = true

    for len(q) > 0 {
        curr := q[0]
        q = q[1:]

        for _, next := range graph[curr] {
            if next == destination {
                return true
            }

            if !visited[next] {
                q = append(q, next)
                visited[next] = true
            }
        }
    }

    return false
}