콘텐츠로 이동

너비 우선 탐색

Breadth First Search(BFS)라고 부르는 너비 우선 탐색은 다음과 같은 절차를 수행합니다.

  1. 각 정점을 방문할 때마다 모든 인접 정점을 검사
  2. 이 중 처음 보는 정점을 방문 예정이라고 기록 한 후, 별도의 위치에 저장
  3. 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문 이 때, a정점에 대해 b, d, f, g라는 인접한 정점이 있었고, b의 정점을 방문할 때, 인접한 정점인 c라는 정점은 d, f, g뒤에 위치해야 함 이를 위해 queue를 사용하면 편함

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략

이 때, 코드는 다음과 같다.

#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;
vector<int> bfs (int start)
{
    vector<bool> discovered(adj.size(), false);
    queue<int> q;

    vector<int> order;
    discovered[start] = true;
    q.push(start);

    while(!q.empty())
    {
        int here = q.front();
        q.pop();
        order.push_back(here);
        for(int i=0; i< adj[here].size(); ++i)
        {
            int there = adj[here][i];
            if(!discovered[there])
            {
                q.push(there);
                discovered[there] = true;
            }
        }
    }
    return order;
}

int main() 
{ 
    adj.resize(7);

    adj[0].push_back(1); adj[0].push_back(3); 
    adj[1].push_back(0); adj[1].push_back(2); adj[1].push_back(4); 
    adj[2].push_back(1); adj[2].push_back(5); 
    adj[3].push_back(0); adj[3].push_back(4); 
    adj[4].push_back(1); adj[4].push_back(3); adj[4].push_back(5);
    adj[4].push_back(6); 
    adj[5].push_back(2); adj[5].push_back(4); 
    adj[6].push_back(4); 

    int startNode = 0; 

    vector<int> result = bfs(startNode); 
    cout << startNode << "번 노드부터 순회 : "; 
    for(int i = 0; i < result.size(); i++) 
    { 
         cout << result[i]; 
         if(i < result.size() - 1) 
             cout << " -> "; 
    } 
    cout << endl;

    startNode = 3; 
    result = bfs(startNode); 
    cout << startNode << "번 노드부터 순회 : "; 
    for(int i = 0; i < result.size(); i++) 
    { 
        cout << result[i];
        if(i < result.size() - 1) 
            cout << " -> "; 
    } 
    cout << endl; 
    return 0; 
}
위의 코드의 입력은 다음과 같다. 첨부파일/algrithm-graph.png

모두 정확히 동작함을 알 수 있다.

이 때 시간 복잡도는 인접 리스트로 구현된 경우 \(O(|V|+|E|)\), 그리고 인접 형렬로 구현했을 경우 \(O(|V|^2)\)입니다.

깊이 우선 탐색과의 다르게 너비 우선 탐색은 그래프에서는 단 한 가지 역할을 하는 데, 최단 경로 문제를 풀 때만 사용한다.

간선 (u, v)에 대해 정점 u에서 정점 v을 발견하여, 먼저 큐에 담았고 가정한다면,

  1. distance[v]=distance[u]+1
  2. 무조건 최단 경로 먼저 조사한다고 가정하기에 큐에 늦게 실린 값은 이전 값보다 최단 경로일 수 없다.
#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;

void bfs2(int start, vector<int> &distance, vector<int> &parent)
{
    distance = vector<int>(adj.size(), -1);
    parent = vector<int>(adj.size(), -1);

    queue<int> q;

    distance[start]=0;
    parent[start]=start;
    q.push(start);
    while(!q.empty())
    {
        int here = q.front();
        q.pop();

        for(int i=0; i<adj[here].size(); ++i)
        {
            int there = adj[here][i];
            if(distance[there]==-1)
            {
                q.push(there);
                distance[there] = distance[here]+1;
                parent[there] = here;
            }
        }
    }
}

vector <int> shortestPath(int v, const vector<int> &parent)
{
    vector<int> path(1,v);
    while(parent[v] != v)
    {
        v=parent[v];
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() 
{ 
    adj.resize(7); 

    adj[0].push_back(1); adj[0].push_back(3); 
    adj[1].push_back(0); adj[1].push_back(2); adj[1].push_back(4); 
    adj[2].push_back(1); adj[2].push_back(5); 
    adj[3].push_back(0); adj[3].push_back(4); 
    adj[4].push_back(1); adj[4].push_back(3); adj[4].push_back(5); 
    adj[4].push_back(6); 
    adj[5].push_back(2); adj[5].push_back(4); 
    adj[6].push_back(4); 

    int startNode = 0;

    vector<int> distance, parent; 

    bfs2(startNode, distance, parent);

    cout << startNode << "번 노드부터의 최단 경로 : " << endl; 

    for(int i = 0; i < distance.size(); i++) 
        cout << "Node " << i << ": " << distance[i] << endl; 


    int targetNode = 5; 
    vector<int> path = shortestPath(targetNode, parent); 

    cout << startNode << "번 부터 " << targetNode << "까지 최단경로 : "; 

    for(int i = 0; i < path.size(); i++) 
    { 
        cout << path[i]; 
        if(i < path.size() - 1) 
            cout << " -> "; 
    } 
    cout << endl; 

    startNode = 3; 
    bfs2(startNode, distance, parent);

    cout << startNode << "번 노드부터의 최단 경로 : " << endl; 

    for(int i = 0; i < distance.size(); i++) 
        cout << "Node " << i << ": " << distance[i] << endl;

    targetNode = 2; 
    path = shortestPath(targetNode, parent); 

    cout << startNode << "번 부터 " << targetNode << "까지 최단경로 : "; 

    for(int i = 0; i < path.size(); i++) 
    { 
        cout << path[i]; 
        if(i < path.size() - 1) 
            cout << " -> "; 
    } 
    cout << endl; 
    return 0; 
}

공부/coding/알고리즘 문제 해결 전략/Sorting Game

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<stack>

using namespace std;

template<typename T>
struct Edge
{
    unsigned int src;
    unsigned int dst;
    T weight;
};

template<typename T>
class Graph
{
public:
    Graph(unsigned int N) : V(N){}
    auto vertices() const {return V;}
    auto &edges() const {return edge_list;}
    auto edges(unsigned int v) const
    {
        vector<Edge<T>> edges_from_v;
        for(auto &e: edge_list)
        {
            if(e.src==v)
                edges_from_v.emplace_back(e);
        }
        return edges_from_v;
    }
    void add_edge(Edge<T>&& e)
    {
        if(e.src>=1&&e.src<=V&&e.dst>=1&&e.dst<=V)
            edge_list.emplace_back(e);
        else
            cerr<<"에러: 유효 범위를 벗어난 정점!"<<endl;
    }
    template<typename U>
    friend ostream& operator<<(ostream& os, const Graph<U>& G);
private:
    unsigned int V;
    vector<Edge<T>> edge_list;
};

template<typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
    for(unsigned int i=1; i<G.vertices(); i++)
    {
        os<<i<<":\t";
        auto edges = G.edges(i);
        for(auto& e : edges)
            os<<"{"<<e.dst<<": "<<e.weight<<"}, ";
        os<<endl;
    }
    return os;
}

template<typename T>
auto create_reference_graph()
{
    Graph<T> G(9);

    map<unsigned int, vector<pair<unsigned, T>>> edge_map;
    edge_map[1]={{2,0},{5,0}};
    edge_map[2]={{1,0},{5,0},{4,0}};
    edge_map[3]={{4,0},{7,0}};
    edge_map[4]={{2,0},{3,0},{5,0},{6,0},{8,0}};
    edge_map[5]={{1,0},{2,0},{4,0},{8,0}};
    edge_map[6]={{4,0},{7,0},{8,0}};
    edge_map[7]={{3,0},{6,0}};
    edge_map[8]={{4,0},{5,0},{6,0}};

    for(auto& i: edge_map)
        for(auto& j : i.second)
            G.add_edge(Edge<T>{i.first, j.first, j.second});
    return G;
}


template<typename T>
auto BFS(const Graph<T>& G, unsigned int start)
{
    queue<unsigned int> queue;
    set<unsigned int> visited;
    vector<unsigned int> visit_order;
    queue.push(start);

    while (!queue.empty())
    {
        auto current_vertex = queue.front();
        queue.pop();

        if(visited.find(current_vertex)==visited.end())
        {
            visited.insert(current_vertex);
            visit_order.push_back(current_vertex);

            for(auto& e : G.edges(current_vertex))
            {
                if(visited.find(e.dst)==visited.end())
                {
                    queue.push(e.dst);
                }
            }
        }

    }
    return visit_order;
}

int main()
{
    using T=unsigned int;

    auto G= create_reference_graph<T>();
    cout<<"[입력 그래프]"<<endl;
    cout<<G<<endl;

    cout<<"[BFS 방문 순서]"<<endl;
    auto bfs_visit_order = BFS(G,1);
    for(auto v : bfs_visit_order)
        cout<<v<<endl;
    return 0;
}