1971. Find if Path Exists in Graph

문제)

n개의 정점을 가진 양방향 그래프가 있습니다.

각 정점은 0부터 n-1까지의 숫자로 라벨링되어 있습니다. 그래프의 간선들은 2차원 정수 배열인 edges로 표현되며,

각 edges[i] = [ui, vi]는 정점 ui와 정점 vi 사이의 양방향 간선을 나타냅니다

각 정점 쌍은 최대 하나의 간선으로 연결되어 있으며, 어떤 정점도 자기 자신에게 간선을 가지지 않습니다.

당신은 주어진 source 정점에서 destination 정점으로 가는 유효한 경로가 존재하는지 확인하려고 합니다.

edges와 정수 n, source, destination가 주어질 때, source에서 destination으로 가는 유효한 경로가 존재하면 true를, 그렇지 않으면 false를 반환하세요.

 

문제 난이도 : 하

 

소요시간 및 풀이)

처음에 unordered_map에 간선 정보를 저장하고 재귀로 풀려다가 시간초과가 발생해서,

벡터에 그래프 정보를 저장하고 큐를 이용해 반복해서 접근하도록 다시 풀었다.

 

소요 시간 : 32분

 

정답 코드

 

class Solution 
{
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) 
    {
        vector<vector<int>> graph(n, vector<int>());

        for (const auto& e : edges)
        {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        vector<bool> visit(n, false);
        visit[source] = true;
        queue<int> q;
        q.push(source);

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

            if (temp == destination)
                return true;

            for (int connect : graph[temp])
            {
                if (!visit[connect])
                {
                    visit[connect] = true;
                    q.push(connect);
                }
            }
        }

        return false;
    }
};