들어가기 전
알고리즘 문제 풀 때 기본은 완전탐색!
완전탐색을 하는데 있어서 항상 bfs를 할지 dfs를 할지 고민을 해야하는 것 같다.
bfs를 써야하는 문제를 풀기전에 개념을 확실히 하려한다.
BFS(너비 우선 탐색)
BFS(너비 우선 탐색)란?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법루트 노드의 자식노드들을 먼저 모두 차례로 방문한 후에, 멀리 떨어져 있는 노드들을 나중에 순회하는 방법을 말해.인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하니까 큐(선입선출)을 활용해.
사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때
ex)
특징
- 직관적이지 않다.
- 재귀적으로 동작하지 않는다.
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
(무한루프에 빠질 위험이 있다.) - 큐(Queue)를 사용한다.
일반적으로 큐를 이용하여 반복적 형태로 구현하는 것이 가장 잘 동작한다. Prim,Dijkstra알고리즘과 유사하다.
과정
* 사진과 같은 그래프를 BFS로 탐색해보자!
- 루트노드(A) 방문 체크 후 큐에 삽입(
offer) - 큐에서 A노드를 꺼낸(
poll) 후 A의 자식노드(B, C, D)들을 방문 체크 후 큐에 삽입(offer) - 이후 차례로 큐에서 하나 씩 꺼낸(
poll) 후, 꺼낸 노드의 자식노드들을 방문 체크 휴 큐에 삽입(offer) - 큐가 비어 있으면(.isEmpty) 반복문 종료
구현
BFS()
큐 생성 = Q;
방문체크 배열 생성
루트노드 큐에 Q.offer;
루트노드 방문체크
while(!Q.isEmpty){
t = Q.poll <-큐의 첫 번째 원소 반환
for(t와 연결된 모든 간선에 대해){
Q.offer()
해당 노드 방문체크
}
}
end BFS()BFS Code(with Java)
public void BFS_Breadth_First_Search(){
// 큐 생성 = queue;
Queue<Integer> queue = new LinkedList<Integer>();
// 방문체크 배열 생성
boolean[] visited = new boolean[nodeCount];
// 루트노드 방문체크 후 큐에 queue.offer;
visited[0] = true;
queue.offer(0);
while(!queue.isEmpty()){
// 큐의 첫 번째 원소 반환
int nowNode = queue.poll();
System.out.print(nowNode + " ");
// 인접 리스트 개수 만큼 반복문
for (int i = 0; i < nodeList[nowNode].size(); i++) {
// 인접 리스트 변수 생성
int adjNode = nodeList[nowNode].get(i);
// 방문 하지 않았으면 방문 체크 후 queue에 삽입
if (!visited[adjNode]){
visited[adjNode] = true;
queue.offer(adjNode);
}
}
}
}시간 복잡도
- 인접 리스트로 표현된 그래프 : O(N+E)
- 인접 행렬로 표현된 그래프 : O(N^2)
