[Algorithm] BFS(너비 우선 탐색)

! DFS에 이은 BFS 공부

1. BFS 동작 방식

DFS의 경우에는 스택 자료구조를 이용하는 반면 , BFS의 경우에는 선입선출 방식인 큐 자로규조를 이용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하며 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

• 동작 방식

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

다음과 같은 그림에서

• 먼저 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다.

• 다음으로 노드 '1'을 큐에서 꺼낸 후, 1과 인접 노드인 2,3을 큐에 삽입한 후 방문 처리를 한다.

• 다음으로 노드 '2'를 큐에서 꺼낸 후, 2와 인접 노드인 7을 큐에 삽입한 후 방문 처리를 한다.

• 다음으로 노드 '3'을 큐에서 꺼낸 후, 3과 인접 노드인 4,5를 큐에 삽입한 후 방문 처리를 한다.

• 이와 같은 과정을 방문하지 않은 인접 노드가 없을 때까지 계속 진행한다.

이로 인한 결과 순서는 1 - 2 - 3 - 7 - 4 - 5 - 6 - 8 이다.

TIP) 실제로 BFS를 구현 함에 있어 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 또한 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이라는 점.

2. BFS 코드 예시

from collections import deque

#BFS 메서드 정의
def dfs(graph, start, visited):

	queue = deque([start])
    	vistied[start] = True     #방문 처리
        
        while queue:
        	v = queue.popleft()
            print(v, end=' ')
            for i in graph[v]:
            	if not visitied[i]:
                	queue.append(i)
                    visited[i] = True
                    
graph = [
	[],
    [2,3],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7,8],
    [2,6,8],
    [6,7]
  ]

visited = [False] * 9

bfs(graph, 1, visited) 		#함수 호출

TIP) 탐색 문제의 경우 그래프 형태로 표현한 다음 풀어보는 것을 고민해보도록!

BFS의 경우에는 레벨 탐색을 하는 경우, 최단 거리를 구할 때 사용한다.