[알고리즘] BFS(Breadth First Search) 너비우선탐색 알고리즘

* 1주차 알고리즘 정리

안녕하세요 감자입니다. 이제 알고리즘정리를 시작하려고 합니다. 오늘알아볼 알고리즘의 종류중 하나인 BFS를 살펴볼것인데요, 많이 쓰이기도하고 중요한 알고리즘인 만큼 정리시작해보겠습니다.

1. BFS(Breadth First Search)는 그래프전체를 탐색하는 알고리즘의 방법중 하나이다.

그래프 전체를 탐색하는 방법은 BFS,DFS가 있다.

BFS(Breadth First Search)는 그래프 전체를 탐색,인접한 노드들을 차례대로 방문한다.

동심원의 형태로 이루어져서 점차 하나씩 모든 노드들을 방문하게 된다. 

BFS에서 가장 중요한 것은 각 노드에 대해서 최단 경로의 길이를 구할 수 있다는것이다. 

이를 구현하기 위해서는 C++ STL Queue 방법을 사용하게 될것이다.

위의 그림대로 살펴보자면 , a->b->c->d->e ....-> k까지의 인접한 노드들을 방문하는것을 알 수 있다.

결국, 노드의 높이에 따라서 모든 노드들을 방문한다고 생각하면 될것이다.

2. BFS의 구현

시작 노드를 Queue에 push해주고 queue가 빌때까지 반복해내가는 방식

(1). Queue에 가장앞에 있는 노드 POP(A의 노드를 맨처음에 PUSH)

(2). 현재 노드의 인접한 모든 노드들중 아직 방문하지 않은 노드들을 Queue에 PUSH

(3). Queue가 비어있지 않으면, 1의 방식대로 다시 시작

* 구현 방식  

(1). 위의 그림대로 설명하면 맨처음에 A를 PUSH 한다. 그리고 그다음 인접노드인 B,C를 PUSH한다.

이때, 가장 맨앞에 있는 노드이므로 A를 POP을 해준다. 

(2). 그리고, 이제 B를 POP 해주고, D와 E를 PUSH해준다. 

(3). C POP해주고, F와 G를 PUSH 해준다.

(4). 이렇게 계속 가다보면 결국엔 A,B,C .... -> K 까지의 값들이 정렬되어서 나온것들을 알 수 있을것이다.

* 인접 리스트 

1. 인접리스트란?

인접 리스트는 그래프의 연결 관계를 vector의 배열(vector<int> adj[])로 나타내는 방식입니다.

BFS를 구현하다보면 인접리스트를 구현할 경우가 있는데 이때, STL VECTOR 로 구현을 하게된다.

왜냐하면 인접리스트를 사용하면, 노드 i에 연결된 노드의 원소를 갖는 VECTOR로 표현 한다.

인접리스트를 사용해야지, 맨처음 First A 의 노드다음인 B에 연결된 노드의 원소를 갖는 간선을 알 수 있다.

* 미로 문제를 풀때 접근 방법

1.하나의 큐를 만든다. (이때 체크할 수 있는 공간을 만들어 놓는다.)

2.위치(0,0) 는 이미 방문한 위치임을 표시하고, 큐에 0,0 위치에 놓는다.

3. 큐가 빌때까지 다음을 반복한다(While(!q.empty())

- 큐에서 하나의 위치 q를 꺼낸다.

- p에서 한칸 떨어진 위치중에서 이동 가능하면서 아직 방문하지 않은 모든 위치들을 방문된 위치라고 표시하고 큐에 넣는다.

- 만약 그 위치가 출구라면 종료한다.

- 그 맵에 속해있는지 확인한다.

Reference: http://sarah950716.tistory.com/12