알고리즘 4-2강. 너비 우선 탐색(Breadth First Search)

[탐색 알고리즘 강좌]

살펴보면서 전진하자!

너비 우선 탐색(BFS, Breadth First Search)

---

이번에는 너비 우선 탐색(BFS, Breadth First Search) 알고리즘에 대해 알아보려고 합니다. 우리가 전에 알게된 깊이 우선 탐색(DFS)과는 달리 스택을 이용하지 않고 큐를 이용하며, 너비 우선 탐색도 트리나 그래프에서의 탐색에 사용되는 알고리즘입니다. 이 너비 우선 탐색은 깊이가 1인 모든 정점을 방문하고 나서, 그 다음에는 깊이가 2인 모든 정점을, 깊이가 3인 모든 정점을 방문하는 식으로 계속 방문하다가 더이상 방문할 곳이 없으면 탐색을 마칩니다. 너비 우선 탐색은 깊이 우선 탐색과는 다르게 무작정 막힐때까지 탐색을 진행하는게 아니라, 이곳저곳 살펴보면서 탐색을 진행하는 것이라고 할 수 있습니다. 우선은, 너비 우선 탐색이 어떻게 이동하는지 보고 특징을 살펴보도록 합시다.

너비 우선 탐색(Breadth First Search)의 방문 순서

깊이 우선 탐색과 마찬가지로 그래프를 통해 방문 순서를 확인하도록 하겠습니다.

이 너비 우선 탐색은 먼저 가까운 정점부터 시작하여 가장 먼 정점까지 방문하기 시작합니다. 깊이 우선 탐색은 스택을 통하여 재귀 호출을 이용한 반면에, 너비 우선 탐색은 방문한 정점의 위치를 기억하기 위해 큐를 이용합니다. 너비 우선 탐색은 예를 들면, 위에서 말한대로와 같이 깊이를 더해가며 방문을 하며 찾으려는 데이터를 찾거나, 더 이상 방문할 곳이 존재하지 않으면 탐색을 마칩니다. 한번 볼까요?

위 그림에서 방문 순서를 보시면 깊이 우선 탐색과 조금 차이가 나죠? 방문 순서는 '1 -> 2 -> 3 -> 4 -> 5 -> 6' 임을 알 수 있습니다. 여기서는 1이 시작점이라고 가정합니다. 우선은 큐가 어떻게 되고, 어떻게 저런 순서가 나올 수 있는지 과정을 모두 살펴보도록 합시다.

(1) 깊이 0은 정점 1밖에 존재하지 않으니 정점 1에서 시작합니다. 큐에는 1이 들어갑니다.

(2) 깊이 1은 정점 2와 정점 3이 존재하며, 큐에서 1을 빼고 2와 3을 삽입합니다.

(3) 깊이 2는 정점 4와 정점 5, 정점 6이 존재하며, 큐에서 2를 빼고 2와 인접한 4, 5를 삽입합니다.

(4) 그리고 큐에서 3을 빼며, 3과 인접한 6을 큐에 삽입합니다. 4는 이미 방문된 상태이므로 탐색할 필요가 없습니다.

(5) 큐에서 4를 빼는데, 이 때 4와 인접한 정점인 2, 3, 5, 6은 이미 방문된 상태이므로 탐색할 필요가 없습니다.

(즉, 큐에 삽입할 정점이 존재하지 않는다는 겁니다.)

(6) 큐에서 5를 빼는데, 이 때 5와 인접한 정점인 2, 4, 6은 이미 방문된 상태이므로 탐색할 필요가 없습니다.

(7) 큐에서 6을 빼는데, 이 때 6과 인접한 정점인 3, 4, 5는 이미 방문된 상태이므로 탐색할 필요가 없습니다.

마지막으로, 과정 7에서 6이 빠져나감으로써 큐가 비어있는 상태가 되어 BFS을 마칩니다. 큐가 비어있다는건, 시작 정점과 연결된 정점들을 모두 탐색했다는 말로써 탐색을 마쳤다고 할 수 있습니다. 이번에는 BFS 알고리즘을 코드로 구현해보도록 하겠습니다. 이번에도, 정점과 정점과의 인접 관계를 알아보기 위하여 간단하게 DFS 알고리즘에 대해 알아볼 때 사용한 인접 행렬을 BFS 알고리즘에서도 사용하도록 하겠습니다.

너비 우선 탐색(Breadth First Search)의 구현

자, 너비 우선 탐색을 이제부터 구현하여 보도록 합시다. 우선은, 정점의 갯수를 N개로 제한한다면 인접 행렬의 크기는 N * N 일 것이며, 큐의 크기도 N(여기서 배열을 큐 형식으로 사용하겠습니다), 방문했음을 표시하는 배열의 크기도 N일 것입니다. 그리고 큐를 이용하니, 전단과 후단 변수를 만들어 두어야 할 것이고 여기서는 큐가 가득찰 일도, 부족할 일도 없다는 상황을 가정하여 큐의 삽입과 제거를 하도록 하겠습니다. 그럼 구현해 보도록 할까요?

#include <stdio.h>

int n; // 입력되는 정점의 최댓값
int rear, front; // 전단과 후단을 나타내는 변수
int map[30][30], queue[30], visit[30]; // 인접 행렬과 큐와 방문 배열

void BFS(int v)
{
	int i;

	visit[v] = 1; // 정점 v를 방문했다고 표시
	printf("%d에서 시작\n", v);
	queue[rear++] = v; // 큐에 v를 삽입하고 후단을 1 증가시킴
	while (front < rear) // 후단이 전단과 같거나 작으면 루프 탈출
	{
		// 큐의 첫번째에 있는 데이터를 제외하고 제외된 값을 가져오며, 전단 1 증가
		v = queue[front++];
		for (i = 1; i <= n; i++)
		{
			// 정점 v와 정점 i가 만나고, 정점 i를 방문하지 않은 상태일 경우
			if (map[v][i] == 1 && !visit[i])
			{
				visit[i] = 1; // 정점 i를 방문했다고 표시
				printf("%d에서 %d로 이동\n", v, i);
				queue[rear++] = i; // 큐에 i를 삽입하고 후단을 1 증가시킴
			}
		}
	}
}

int main()
{
	int start; // 시작 정점을 나타내는 변수
	int v1, v2;

	scanf("%d%d", &n, &start);

	while (1)
	{
		scanf("%d%d", &v1, &v2);
		if (v1 == -1 && v2 == -1) break;
		map[v1][v2] = map[v2][v1] = 1;
	}
	BFS(start); // BFS 시작!

	return 0; 
}

결과:

6 1

1 2 1 3 2 4 2 5 3 4 3 6 4 5 4 6 5 6 -1 -1
1에서 시작
1에서 2로 이동
1에서 3로 이동
2에서 4로 이동
2에서 5로 이동
3에서 6로 이동

이해를 돕기 위해 핵심이 되는 코드 옆에 모두 주석을 달아놓았습니다. 그리고, 시간이 나신다면 DFS를 그래프 혹은 트리 같은 자료구조로 구현하는 참에 BFS도 함께 구현을 해보시면 큰 도움이 될 것 같습니다. 요번에는, DFS가 아닌 BFS를 통해서 최단 경로의 길이를 구하는 코드를 함께 구현해보도록 합시다.

너비 우선 탐색(BFS)를 통한 최단 경로 길이 구하기 설계

아래 그림의 도로에서 최단 경로의 길이를 구하는 알고리즘을 설계해보도록 합시다.

위 그림에서 S는 시작(Start) 지점이며, F는 도착(Final) 지점입니다. 그리고 회색으로 칠해진 칸은 이동할 수 없는 영역, 흰색으로 칠해진 칸은 이동 가능한 영역인거 말 안해도 너무나 잘 알고 계실겁니다. 그럼 바로, 시작점에서 도착점까지 최단 경로의 길이를 구하는 것을 이번에는 BFS를 통해 구해봅시다.

모든 경로의 길이를 구하면 위와 같으며, 길이가 3인 지점에서 두 갈래의 길로 나뉘게 되는데 여기서는 큐에 길이가 4인 지점의 좌표를 모두 큐에 넣습니다. 그러고 나서 큐에서 하나씩 꺼내서, 그 지점과 근접한 방문하지 않은 지점을 방문하게 되는것 입니다.

BFS 알고리즘을 통해 최단 경로의 길이를 구하려면 역시 큐가 필요한데 위의 도로가 2차원 배열으로 표현할 수 있으므로 x와 y 좌표를 기억할 배열, 그리고 길이를 나타내는 l를 기억할 배열이 필요합니다. 이 세 배열을 큐 형식으로 사용하도록 하고 반복문을 통해 도착 지점에 도착하거나 모든 지점을 방문하면 빠져나오도록 하여야 하겠죠? 우선 이를 코드로 한번 구현하여 보도록 합시다.

너비 우선 탐색(BFS)를 통한 최단 경로 길이 구하기 구현

우선 길이가 N으로 주어지면, 크기가 N*N인 2차원 배열을 만들도록 합시다. 그리고 좌표와 길이를 담기 위해 크기 N를 차지하는 배열을 만들도록 합시다. 이제, BFS를 통해 최단 경로 길이를 구하는 코드를 작성해보도록 합시다.

#include <stdio.h>

int n, cnt; // 맵의 크기와 카운트 변수
int map[10][10]; // 맵을 나타내는 2차원 배열
int x[100], y[100], l[100]; // 좌표와 길이를 담을 배열

// 큐에 좌표 정보와 길이를 삽입하는 함수
void enqueue(int _x, int _y, int _l)
{
	x[cnt] = _x;
	y[cnt] = _y;
	l[cnt] = _l;
	cnt++;
}

void BFS(int _x, int _y)
{
	int pos = 0;

	// 시작점의 좌표 정보와 길이를 큐에 삽입한다
	enqueue(_x, _y, 1);
	// 더 이상 방문할 지점이 없거나, 도착 지점에 도착하면 루프를 탈출한다
	while (pos < cnt && (x[pos] != n - 1 || y[pos] != n - 1))
	{
		// 두 번 방문하게 하면 안되므로, 이미 지나갔다는 표시를 해둔다
		map[y[pos]][x[pos]] = 0;

		// 위로 갈 수 있다면, 위 지점의 좌표 정보와 길이를 큐에 삽입한다
		if (y[pos] > 0 && map[y[pos] - 1][x[pos]] == 1)
			enqueue(x[pos], y[pos] - 1, l[pos] + 1);
		// 아래로 갈 수 있다면, 아래 지점의 좌표 정보와 길이를 큐에 삽입한다
		if (y[pos] < n - 1 && map[y[pos] + 1][x[pos]] == 1)
			enqueue(x[pos], y[pos] + 1, l[pos] + 1);
		// 왼쪽으로 갈 수 있다면, 왼쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
		if (x[pos] > 0 && map[y[pos]][x[pos] - 1] == 1)
			enqueue(x[pos] - 1, y[pos], l[pos] + 1);
		// 오른쪽로 갈 수 있다면, 오른쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
		if (x[pos] < n - 1 && map[y[pos]][x[pos] + 1] == 1)
			enqueue(x[pos] + 1, y[pos], l[pos] + 1);

		// 큐의 다음 순서의 지점을 방문한다
		pos++;
	}

	// cnt가 pos보다 크다면, 도착 지점에 무사히 도착한 것이라고 말할 수 있다.
	// 위의 반복문은 도착점에 도착하게 되면 루프를 바로 빠져나오기 때문에,
	// 길이를 삽입하는 큐의 마지막 요소가 최단 경로의 길이라고 할 수 있다.
	if (pos < cnt)
		printf("최단 경로 길이: %d\n", l[pos]);
}

int main()
{
	int i, j;

	scanf("%d", &n);
	min = n * n;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			scanf("%d", &map[i][j]);
	BFS(0, 0); // BFS 시작!

	return 0;
}

결과:

6
1 1 1 1 1 1
0 0 1 0 0 1
1 1 1 0 1 1
1 0 0 0 1 0
1 1 1 0 1 0
0 0 1 1 1 1
최단 경로 길이: 13

이해하기 어려운 부분은 주석을 한번 참고해보세요. 미흡한 설명이지만 그래도 이해에 도움이 되셨으면 좋겠습니다.

위 그림을 보시면 (2, 0)에서 두 갈래로 갈리면서 큐에 삽입되고 있는게 보이실겁니다. 점점 길이와 좌표가 변하다가, 도착점인 (5, 5)에서 루프를 벗어나 최단 경로의 길이를 출력하게 되는 것입니다. 길이를 보시면 (5, 5) 까지 가는데 가장 짧은 경로의 길이가 13이라는 것이라고 할 수 있습니다.

그런데, 너비 우선 탐색을 설명하기 위해 쓰인 예제 코드 내에서는 일반 배열을 큐 형식으로 사용하게 되는데 이 때는 위 그림처럼 방문한 좌표를 저장하고 그대로 남아 메모리 공간에서 해제가 되지 않고 있으므로 메모리를 많이 잡아먹습니다. 왠만하면 큰 크기의 영역에서는 큐를 직접 만드셔서 쓰시는것이 낫습니다. 오늘은 너비 우선 탐색에 대한 설명은 여기까지 하도록 하고, 다음 강좌에서는 백트래킹(Backtracking)에 대해 알아보려고 합니다. 부족한 강좌 여기까지 읽어주셔서 감사하고, 모두 수고하셨습니다.