그래프 순회 문제
- 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제
- EX) 사무실에서 출발하여 주변 거래처를 순회하며 결재를 하는 경우
- 그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제라고도 부른다.
- 여러 그래프 탐색 알고리즘이 존재하고, 각각은 서로 다른 순서로 모든 정점을 방문하다.
너비 우선 탐색(BFS, Breadth-First Scrach)
- 시작 정점을 경계(frontier)에 추가하는 것으로 시작
- 경계는 이전에 방문했던 정점들에 의해 구성된다
- 그리고 현재 경계에 인접한 정점을 반복적으로 탐색한다
- 같은 거리에 있는 정점들의 방문 순서는 임의로 정해도 되지만, 멀리 있는 정점보다는 가까운 정점을 먼저 방문해야 한다.
- BFS는 모든 정점에 대해 자식 정점을 손자 정점보다 먼저 방문한다는 점이 중요한 특징이다.
BFS의 구현
이 글에서 다루는 BFS 말고도 깊이 우선 탐색(DFS)가 존재하는데, 보통 BFS와 DFS를 크게 두 가지 방식으로 구현한다.
하나는 인접 행렬이고, 하나는 인접 리스트이다.
인접 행렬의 경우 [자료구조] 파트에서 다뤘던 것처럼 배열을 만들고 연결된 노드에 해당하는 인덱스에 값(가중치)을 저장한다.
인접 리스트의 경우 연결되어 있는 에지만 저장한다. 두 가지 방식으로 BFS와 DFS를 구현할 수 있지만, 시간 복잡도와 공간 복잡도 측면에서 차이점이 존재한다. 이에 대한 자세한 내용은 아래에서 다룰 예정이다.
필자가 참고하는 교재에서는 일반적인 인접 리스트 구현과는 다르게, 에지 리스트를 통해서 특이하게 구현하였다. 결국에는 인접 리스트와 시간 복잡도, 공간 복잡도는 동일하지만, 인접 리스트에서는 vector를 사용하여 구현하고, 에지 리스트 기반 구현에서는 pair를 사용한다.
참고로 에지 리스트 기반 구현은 PS에서 사용하기에는 오래 걸리므로, 인접 리스트나 인접 행렬을 통해서 문제를 푸는 것을 추천한다.
에지 리스트를 통한 구현
Edge 구조체와 Graph 클래스 : 크루스칼 MST 알고리즘에서 다뤘던 코드 그대로 사용한다.
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>
using namespace std;
template <typename T>
struct Edge
{
unsigned src;
unsigned dst;
T weight;
};
template <typename T>
class Graph
{
public:
// N개의 정점으로 구성된 그래프
Graph(unsigned N) : V(N) {}
// 그래프의 정점 개수 반환
auto vertices() const { return V; }
// 전체 에지 리스트 반환
auto& edges() const { return edge_list; }
// 정점 v에서 나가는 모든 에지를 반환
auto edges(unsigned 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)
{
// 에지 양 끝 정점 ID가 유효한지 검사
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 V; // 정점 개수
vector<Edge<T>> edge_list;
};
template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
for (unsigned 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, 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 breadth_first_search(const Graph<T>& G, unsigned start)
{
queue<unsigned> queue;
set<unsigned> visited; // 방문한 정점
vector<unsigned> 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;
// 그래프 객체 생성
auto G = create_reference_graph<T>();
cout << "[입력 그래프]" << endl;
cout << G << endl;
// 1번 정점부터 BFS 실행 & 방문 순서 출력
cout << "[BFS 방문 순서]" << endl;
auto bfs_visit_order = breadth_first_search(G, 1);
for (auto v : bfs_visit_order)
cout << v << endl;
}
에지 리스트 기반 BFS의 시간 복잡도 : O(V + E)
- 정점 방문 시간 복잡도:
- 모든 정점을 한 번씩 방문하므로 O(V)
- 간선 탐색 시간 복잡도:
- 각 정점에서 나가는 모든 간선을 확인하기 위해 edges(unsigned v) 메소드를 호출한다. 이 메소드는 전체 간선 리스트를 탐색하므로, 각 호출당 시간 복잡도는 O(E)
- 하지만, 전체 간선 리스트를 탐색하더라도 각 간선을 한 번씩만 처리한다. 즉, 모든 간선을 한 번씩만 방문하므로, 전체 간선 탐색 시간 복잡도는 O(E)
따라서, BFS의 전체 시간 복잡도는 O(V)+O(E) 가 된다
인접 행렬으로 구현한 BFS
인접 행렬을 이용해서 그래프를 표현하고, 배열에 방문 여부를 기록하며 순회한다.
이 코드는 외워질 정도로 반복해서 코드를 작성해보는 것을 추천한다
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
// 입력
int board[502][502] =
{{1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
// 방문 기록
bool vis[502][502];
int n = 7, m = 10;
// [x][y]라고 생각하고, x를 row, y를 column으로 생각하자
// 아래, 오른쪽, 위, 왼쪽 순서라고 가정
// 아래(x + 1), 오른쪽(x), 위(x - 1), 왼쪽 (x)
int dx[4] = {1, 0, -1, 0};
// 아래(y), 오른쪽(y + 1), 위(y), 왼쪽(y - 1)
int dy[4] = {0, 1, 0, -1};
// BFS에서는 그래프를 저장할 자료구조(여기서는 NXM 인접 행렬), 방문 기록, 방문할 곳을 저장할 queue 총 3가지가 필요함을 기억하자
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// 방문할 곳을 저장할 queue를 만들자
queue<pair<int, int>> que;
// (0, 0)을 반복했다고 명시하고, 아래에서 반복문을 통해 원하는 결과를 얻는다.
vis[0][0] = 1;
que.push({0, 0}); // 큐에 시작점을 push
// 현재 위치를 큐에서 꺼내서 설정해주고, 주변을 순회하며 방문하지 않은 곳이 있으면 방문을 체크하고 큐에 push
while (!que.empty()) { // 더 이상 방문할 곳이 없을 때 까지
auto cur = que.front(); // 현재 위치를 얻는다
que.pop();
cout << '(' << cur.X << ", " << cur.Y << ") -> ";
for (int dir = 0; dir < 4; dir++) { // 인접 행렬 내 현재 위치에서 상하좌우를 살피겠다.
int nx = cur.X + dx[dir]; // nextX 좌표
int ny = cur.Y + dy[dir]; // nextY 좌표
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 탐색하는 점이 행렬의 범위를 벗어난 경우
if (vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 노드이거나 연결되어 있지 않는 노드인 경우
vis[nx][ny] = 1; // 이미 방문했다고 명시. 반드시 que에 push 할 때 같이 방문 기록을 남겨야 함
que.push({nx, ny});
}
}
}흐름
(편의를 위해서 first 대신 X, second 대신 Y를 쓸 수 있도록 하고, 변위 값을 배열로 저장해두면 좋다)
- 그래프를 표현할 자료구조(인접 행렬), 방문 여부를 기록할 배열, 방문할 곳을 저장할 queue 총 3가지가 필요하다.
- 출발점을 방문했다고 기록하고, queue에 push한다.
- queue가 빌 때 까지(더 이상 순회할 노드가 없을 때 까지) 다음을 반복한다.
- queue를 pop해서 현재 위치를 얻는다
- 현재 위치에서 움직일 수 있는 상하좌우(위 코드는 아래, 오른쪽, 위, 왼쪽 순서)에 대해서 루프를 돈다
- 인접 행렬의 범위를 벗어나면 스킵
- 이미 방문했거나, 연결되어 있지 않는 노드라면 스킵
- 1, 2번의 조건에 해당되지 않아 스킵되지 않은 경우 방문 배열에 해당 위치를 방문했다고 기록하고, queue에 현재 위치를 push한다. (다음에 방문할거야~)
주의해야 할 점
- 출발점에 방문했다는 기록을 남겨야 한다.
- 방문했다는 기록을 pop할 때 해버리면 안 된다. push할 때 해야 한다.
- 이유 Ex) (0,0)과 (1, 0), (2, 0), (3,0)이 연결 되어있고, (1,0) - (1,1), (2,0) - (1,1)이 연결되어 있는 상황을 생각해보자.
- 만약 pop할때 방문 여부를 기록하게 된다고 치자.
- BFS에서는 (1,0) 다음 (2,0)을 방문한다.
- (1,0)에서 (1,1)을 push한다. 그리고 (2,0)에서 또 (1,1)을 push하게 된다. 즉 같은점이 큐에 여러 번 들어가게 되서 시간 초과나 메모리 초과가 발생할 수 있게 된다.
- 만약 push할 때 방문 여부를 기록하게 된다면 (2,0)에 방문했을 때 중복해서 (1,1)을 push 하는 일이 없어질 것이다.
- 3-2 과정에서 범위를 벗어났는지, 방문했는지, 연결되어 있는지에 대한 체크를 하는데, 이 3가지 조건 중 하나라도 누락하면 안 된다
인접 리스트를 이용한 BFS 구현
인접 행렬 대신 인접 리스트를 사용한다는 점에서 차이점이 존재하고, 나머지 흐름은 거의 유사하다.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
bool vis[MAX];
vector<int> adj[MAX];
queue<int> que;
int main(void) {
int n, m, start; // n : 노드의 수, m : 간선(에지)의 수, v : 출발점 Indecur
cin >> n >> m >> start;
for (int i = 0; i < m; i++) {
int s, e;
cin >> s >> e;
// 무향 그래프라 양방향으로 push
adj[s].push_back(e);
adj[e].push_back(s);
}
vis[start] = 1;
que.push(start);
while (!que.empty()) {
int cur = que.front();
que.pop();
for (int i = 0; i < adj[cur].size(); i++) { // cur에 연결되어 있는 노드에 대해서 순회
int next = adj[cur][i];
if (!vis[next]) {
vis[next] = true;
que.push(next);
}
}
}
}
만약 인접 리스트의 원소들을 차례대로 방문하기 원하는 경우에는 각 노드에 연결되어 있는 노드들에 대해서 정렬해주고 BFS 하면 된다.
방문 순서를 다뤄야 해서 배열에 저장해야 할 필요가 있는 경우에는 vector를 만들어서 int cur = que.front()로 현재 위치를 받아올 때 방문 vector에 push 해주자.
'Algorithm > Graph' 카테고리의 다른 글
| [Algorithm/Graph] 벨만-포드 알고리즘(Bellman-Ford algorithm)과 음수 가중치 사이클 찾기 (0) | 2024.07.13 |
|---|---|
| [Algorithm/Graph] 다익스트라 최단 경로 알고리즘(Dijkstra's algorithm) (0) | 2024.07.13 |
| [Algorithm/Graph] 프림의 최소 신장 트리 알고리즘(prim's algorithm) (0) | 2024.07.13 |
| [Algorithm/Graph] 이분 그래프(bipartite graph) 판별하기 (0) | 2024.07.13 |
| [Algorithm/Graph] 깊이 우선 탐색(DFS, Depth-First scrach) (0) | 2024.07.12 |