너비 우선 탐색

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

각 정점을 방문할 때마다 모든 인접 정점을 검사
이 중 처음 보는 정점을 방문 예정이라고 기록 한 후, 별도의 위치에 저장
인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문 이 때, 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을 발견하여, 먼저 큐에 담았고 가정한다면,

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

#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; 
}

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;
}

Bloodmoon

Bloodmoon

탐색기

너비 우선 탐색

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

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

그래프 뷰

목차