그래프(Graph), 넓이 우선 탐색(BFS), 깊이 우선 탐색(DFS)

잡학다식을꿈꾼다 2022. 9. 17. 00:17

그래프(Graph)는 각 정점(Vertex)와 간선(Edge)로 이루어진 자료구조이다. 그래프는 실생활에서도 많이 접할 수 있다. 버스 노선도, 지하철 노선도도 일종의 그래프이다. 그래프는 자료 구조 중에서도 가장 근본적인(?) 자료 구조라고 볼 수 있다. 그 예로 리스트(List)의 경우에도 구성을 보면 하나의 노드(Node)에 데이터와 다음 혹은 이전의 노드에 대한 정보를 저장하고 있어서 서로 연결되어 있다는 점에서 그래프의 정의라고 볼 수 있다. 트리 역시 루트 노드(Root Node)를 시작으로 밑에 자식 노드(Child Node)들이 연결되어 구성된다는 점에서 간선에서 제약 사항이 있는 그래프라고 볼 수 있다.

그래프를 표현하는 방식에는 인접행렬로 표현하는 것과 인접리스트로 표현하는 방식이 있다. 인접행렬로 표현하는 방식은 각 노드를 2 차원 배열로 만든 후, 대응되는 노드들 사이에 간선이 있으면 이를 true, 아니면 false 값을 저장하는 것이다. 인접 행렬은 모든 정점에 대한 간선 정보를 포함하고 있기에, 연결 정보를 파악하는 것이 O(1)으로 빠르고, 구현이 용이하다는 것이 장점이다. 다만 노드의 수가 많아지게 되면 노드 수의 제곱에 비례하여 저장 공간을 요구하게 된다는 점은 단점으로 작용하고 있다.

인접 리스트는 반면에 하나의 노드에 연결된 모든 노드를 저장한 리스트를 원소로한 리스트로 구성되어 있다. 말이 복잡한데 그림을 보면 쉽게 이해할 수 있을 것이다. 인접 리스트의 장점은 딱 필요한 만큼만 저장 공간을 요구하는 것과 연결 정보에 대해서 O(n)이라는 비교적 합리적인 시간을 소요한다는 것이다. 다만 인접 행렬 방식에 비해서는 구현이 어렵다는 것이 단점이다.

그래프에 대해서 이야기 하고자 하면 더 이야기할 수 있지만 그래프 자체에 대해서는 여기까지만 언급하기로 하자. 그래프가 노드+간선으로 이루어져 있고, 추가적으로 다양한 형태의 자료구조를 저장할 수 있는 수용성을 가지고 있다 정도만 기억하자. 이정도만 해도 그래프가 뭔지 몰라서 코딩 테스트 문제를 풀 지 못하는 일은 없을 것이다.(특수한 형태의 그래프에 대해서는 추후 코딩 테스트 문제를 풀다가 다루게 될 일이 있으면 한 번 다루어 보겠다!!) 대신 그래프 관련 문제에서 주요하게 다루고 있는 부분들 중 탐색에 대해 다룰 것이다.

그래프에서의 탐색(Search) 방식에 대해 이야기를 해보고자 한다. 코딩 테스트에서는 아마 이 부분이 그래프 자체에 대한 내용보다 더 중요하다고 생각한다. 가장 기본적인 형태의 그래프는 노드 간의 차이가 없다. 트리처럼 자식 노드나 부모 노드 처럼 계층이 나누어져 구분되어 있지 않다는 의미이다. 그러한 이유로 그래프의 탐색은 그래프에 속한 노드의 순회와 연결된다. 그러면 여기서 문제는 어떻게 효율적으로 그래프를 순회할 것인가이다.

하나의 노드에 대해 중복된 방문은 지양해야 한다. 불필요한 동작일 뿐더러, 자칫하면 특정 노드들만으로 구성된 회로 안에 가쳐서 더이상 탐색을 진행하지 못하는 일이 발생할 수도 있다. 중복을 최대한 피하면서 각 노드들을 순회하는 방법으로 넓이 우선 탐색 방식(BFS)과 깊이 우선 탐색 방식(DFS)을 들고자 한다.

넓이 우선 탐색 방식은 시작하는 노드부터 가까운 노드 순대로 탐색을 진행하고 옆으로 갈 곳이 없다면 아래로 내려가자는 것이다. 자세한 것은 밑의 이미지를 보면 이해가 될 것이다.

큐(Queue)를 이용하면 BFS 함수를 구현할 수 있다. 이에 대해서는 밑에서 코드로 직접 구현하여 보여줄 것이다.

깊이 우선 탐색 방식(DFS)는 BFS와 다르게 하나의 노드에서 그 노드가 갈 수 있는 제일 먼 노드까지 간 후, 더 이상 갈 곳이 없으며 그 옆의 노드로 이동하는 방식으로 구현된다. 다음의 이미지를 참고해라.

DFS 함수는 재귀함수의 형태를 띄고 있다. 더 자세한 사항은 밑에서 구현할 코드를 참고해 주길 바란다.

직접 BFS, DFS를 구현해 보자. 우선 그래프를 구현하였는 데 2 차원 배열로 구현하였다. 0의 경우 간선이 없는 노드, 1의 경우 인접한 1 혹은 2 노드를 정점으로 한 엣지를 가진 노드. 2의 경우 1 노드와 같으나 최종적으로 탐색할 노드이다. 두 형태로 탐색을 한 후, 탐색한 결과와 탐색하는 데 걸리는 시간을 출력하는 코드이다. 코드는 아래와 같다.

#include <iostream>
#include <queue>
#include <string>
#include <sstream>
#include <chrono>

//시간 측정을 위한 함수
unsigned long int howLong(std::pair<int, int> (*fptr)(int), int data) {
	std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
	fptr(data);
	std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
	std::chrono::nanoseconds nano = end - start;
	return nano.count();
}


struct Node {
	int data;
	bool visited;
};

//movement : 0=right, 1=left, 2=down, 3=up(바둑판 모양으로 edge가 남)
std::pair<int, int> movements[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

Node graph[10 + 2][10 + 2] = { {{0, false}, }, }; // 노드는 100x100 개 있는 것고 배열상 인접한 노드들끼리 연결되어 있다.

//BFS(넓이 우선 탐색) : 있으면 배열상 위치가 나오고, 아니면 (-1, -1)
std::pair<int, int> BFS(int toFind) {
	std::queue<std::pair<int, int>> queue;

	queue.push({1, 1}); // 시작
	graph[1][1].visited = true;

	while (!queue.empty()) {
		std::pair<int, int> nowLoc = queue.front();
		queue.pop();

		for (int i = 0; i < 4; i++) {
			std::pair<int, int> toGo = 
				{ nowLoc.first + movements[i].first, nowLoc.second + movements[i].second };
			if (graph[toGo.first][toGo.second].data == 0) {
			} // edge가 없는 부분(편의상 만듦)
			else if (!graph[toGo.first][toGo.second].visited) {
				graph[toGo.first][toGo.second].visited = true; // 간 곳 표시
				if (graph[toGo.first][toGo.second].data == toFind) {
					return toGo;
				}
				queue.push(toGo); 
			}
		}
	}

	return {-1, -1};
}

//DFS

std::pair<int, int> result = { -1, -1 };

void semi_DFS(std::pair<int, int> nowLoc, int toGo) {
	if (result.first != -1) {
		return;
	}
	else if (graph[nowLoc.first][nowLoc.second].data == toGo) {
		result = nowLoc;
		return;
	}
	else {
		std::pair<int, int> res = {-1, -1};
		for (int i = 0; i < 4; i++) {
			std::pair<int, int> next =
				{ nowLoc.first + movements[i].first, nowLoc.second + movements[i].second };

			if (graph[next.first][next.second].data == 0); // edge가 없는 부분(편의상 만듦)
			else if (!graph[next.first][next.second].visited) {
				graph[next.first][next.second].visited = true; // 간 곳 표시
				semi_DFS(next, toGo);
			}
		}
		return;
	}
}

std::pair<int, int> DFS(int toGo) {
	semi_DFS({1,1}, toGo);
	return result;
}

//처음 상태로 만들어줌
void reset() {
	for (int i = 1; i < 11; i++) {
		for (int j = 1; j < 11; j++) {
			graph[i][j].visited = false;
		}
	}
}

int main() {
	std::string str;
	std::stringstream ss;

	std::cout << "Normal Node : 1, To Go : 2, Node without edge : 0" << std::endl;

	char input;
	for (int i = 1; i < 11; i++) {
		std::getline(std::cin, str);
		ss << str;
		for (int j = 1; j < 11; j++) {
			ss >> input;
			graph[i][j].data = input - 48;
		}
		str.clear();
		ss.clear();
	}

	std::cout << std::endl;

	for (int i = 1; i < 11; i++) {
		for (int j = 1; j < 11; j++) {
			std::cout << graph[i][j].data << ' ';
		}
		std::cout << std::endl;
	}

	std::cout << std::endl;

	std::pair<int, int> bfs = BFS(2);
	reset();
	unsigned long int t1 = howLong(BFS, 2);
	reset();
	std::cout << "BFS 위치 : " << bfs.first << " " << bfs.second << " 시간 : " << t1 << std::endl;

	std::pair<int, int> dfs = DFS(2);
	reset();
	unsigned long int t2 = howLong(DFS, 2);
	reset();
	std::cout << "DFS 위치 : " << dfs.first << " " << dfs.second << " 시간 : " << t2 << std::endl;

	return 0;
}

임의로 여러 개의 입력을 놓고 비교해본 결과 원래 그런건지 모르겠지만 DFS의 성능이 압도적으로 좋았다. 상대적으로 여러개의 자료구조(?)를 사용해서 그런지는 모르겠는데 BFS의 성능은 그렇게 좋지는 않았다. 다만 지금은 10x10 그래프 맵이지만 압도적으로 맵의 사이즈가 커지고 중앙부에 목적지가 위치해 있을 경우, DFS 함수가 오버로드 되었다.(오버로드는 내 미숙함 때문인것 같다 ㅠㅠ) 결과는 다음과 같다.

결과는 이렇다. 내가 만약 그래프에서 탐색 알고리즘을 쓸 일이 생기면 대부분의 경우에 대해서 DFS를 사용할 것이다. 모든 경로를 방문하는 경우나 특정 값이 위치한 곳을 찾을 때는 DFS가 훨씬 빠르고 구현이 쉽기 때문이다. 경로 특징을 기억해야하는 문제라면 나는 반드시 DFS를 사용해야할 것이다. 반면 최단 경로를 결정해야 하는 문제라면 BFS를 쓸 것이다. 넓게 탐색하는 특징 때문에 결과가 나온다면 높은 확률로 최단 거리일 확률이 높기 때문이다. 이 것으로 글을 마치도록 한다.