Media Log

[탐색 알고리즘 강좌]


살펴보면서 전진하자!

너비 우선 탐색(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)에 대해 알아보려고 합니다. 부족한 강좌 여기까지 읽어주셔서 감사하고, 모두 수고하셨습니다.

저작자 표시 비영리 변경 금지
신고
  1. 지나가던 사람 at 2014.01.24 21:21 신고 [edit/del]

    오타인줄 알았는데 전부다 Breath로 써놓으셨네요..
    BFS는 Breadth First Search 입니다.

    Breath는 숨이라는 뜻이고,
    Breadth는 너비라는 뜻입니다.

    혹시나 다른 사람들이 보고 착각할까봐,, 끄적여봅니다..

    Reply
  2. 지나가던 사람2 at 2014.08.16 02:40 신고 [edit/del]

    좋은 자료 감사합니다.
    이렇게 그림과 도표로 알기 쉬운 문서를 만든다는 게, 정말 쉬운일은 아닐텐데요.

    덕분에 개념 정리 쉽게 하고 갑니다.

    Reply
  3. justant at 2014.08.20 15:11 신고 [edit/del]

    아직 다 읽어 보진 않았지만 깔끔하게 정리가 잘 되어 있네요
    블로그 포스팅이 쉬운게 아닌데,,, 감사합니다^^

    Reply
  4. bb at 2014.10.26 13:19 신고 [edit/del]

    cnt 초기값은 안주어줘도 되는 건가요?
    min은 어디에 사용되나요?

    Reply
    • aa at 2014.12.23 20:04 신고 [edit/del]

      cnt처럼 전역변수 선언시 자동으로 0으로 초기화됩니다.
      min은 BFS()가 call되는 횟수보다 무조건 크거나 같기때문에 이를 이용하여 예외처리를 하려고 하신 것 같은데 if(pos<cnt)에서 이미 걸러져서 나중에 필요 없다고 생각하시고 지운 듯 합니다.

  5. ㅁㅁ at 2015.03.13 11:14 신고 [edit/del]

    감사합니다. 잘 보고 갑니다.

    Reply
  6. dsd at 2015.08.06 21:00 신고 [edit/del]

    DFS같은 경우는 재귀로 탐색하다보니까 각각의 케이스에 따른 최단경로 를 관리하는게 쉬웠는데, BFS는 큐를 사용해서 구현하니 노드가 여러개로 갈라질때 각각의 케이스의 cost값을 어떻게 관리하나 봤더니...
    모듈로 따로 만들어서 같이 관리하니까 편해지는군요..ㅎㅎㅎ 잘보고 갑니다.

    Reply
  7. ㅁㄴㅇㄹ at 2015.08.12 18:09 신고 [edit/del]

    소스코드 주석에 잘못된게 있는데요,

    3번째 줄에 int n; // 입력될 정수의 갯수
    입력될 정수의 갯수가 아니라, 정점의 최대값이 되어야 할것 같습니다.

    만약에 입력될 정점의 숫자보다 더 큰 정점값이 들어가게 되면
    18줄의 for 문에 n까지 연산을 하는데, 그러면 정점의 갯수보다 큰 값을 만나면 출력하지 않고 끝납니다.

    ex)정수 입력
    6 2
    2 4 2 6 4 8 4 10 6 8 6 12 8 10 8 12 10 12 -1 -1
    을 입력하게 되면

    2 에서 시작.
    2에서 4로 이동
    2에서 6로 이동

    으로 끝이 납니다.
    n = 6인데, 중간 정점값이 8이 들어와, 거기까지 연산을 진행하지 못하고 끝을 내버리게 됩니다.

    ps. 위의 입력값은 올리신 값의 2배로 넣은 값입니다.
    좋은 내용 감사합니다. 덕분에 공부해서 갑니다

    Reply
    • BlogIcon EXYNOA at 2015.08.13 00:37 신고 [edit/del]

      입력될 정수의 갯수라는 주석이 어디서 날아온 건지 모르겠네요..

      말씀대로 주석을 수정하였습니다. 감사합니다 ^-^)/

      P.S 댓글로 보고되는 것만 해도 일부 강좌 게시글에서 결과가 다른 강좌 게시글의 결과가 복사되어 들어가거나 주석이 엉뚱하게 들어가는 경우가 좀 있는 것 같습니다.. 블로그 관리가 12월 까지는 힘들어서 즉각 수정이 이루어지지 않는점 양해 부탁드립니다. (_ _)/

  8. hyss4412 at 2016.01.23 13:56 신고 [edit/del]

    100 100 인데 모두 채워져있는 경우에는 답이 유추되지 않습니다. 확인해 보시는게 좋을 것 같습니다.

    Reply
  9. Grace at 2016.02.20 13:28 신고 [edit/del]

    설명과 코드가 완전 도움됩니다. 잘 정리해 주셔서 감사합니다.

    Reply
  10. c초보 at 2016.03.12 13:24 신고 [edit/del]

    와 정말 정리 잘해놓으셨네요~ 감사합니다 잘읽고 갑니다.

    Reply
  11. enzyme at 2016.04.13 18:58 신고 [edit/del]

    BFS 함수의 마지막 출력 부분에
    if (pos< cnt) 조건문은 없어도 되지 않나요??? 이해가 잘 안되네요.
    노드가 갈라지는 level이 pos라 생각하면 당연히 cnt가 level보다 클거라 생각합니다.
    아닐 경우도 있어서 조건문이 있는건가요???


    Reply
  12. kim at 2016.10.15 15:50 신고 [edit/del]

    좋은 정보 감사합니다.
    근데 row와 column이 다 바뀌어있는게 아닌가요?

    Reply
  13. hugh at 2017.10.11 10:04 신고 [edit/del]

    대단 하십니다.~ㅋ

    Reply

submit

티스토리 툴바