[자료구조] 너비우선탐색(BFS)

BFS란?

• Breadth-First Search로 너비 우선 탐색 알고리즘이라고도 한다.
• 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
• 그래프를 순회하는 알고리즘 즉, 그래프를 방문한다.
• 그래프의 모든 정점과 간선을 방문해야한다.
• 드라마로 예를 들었을 때, DFS는 한 드라마만 골라서 주구장창 본다고 하면, BFS는 여러 드라마를 한 번에 보는 느낌
• DFS에는 Back edge, BFS에는 Cross edge가 있다.
• DFS에선 Stack, BFS에서는 Queue를 이용한다.

---

Properties of BFS

 Notation

    Gs : s의 연결된 구성요소

 Property 1

    BFS(G, s)는 Gs의 모든 정점(vertex)과 간선(edge)을 방문한다.

 Property 2

    BFS(G, s)에 의해 형성된 discovery edge는 Gs의 spanning tree Ts를 형성한다.

       +) spanning Tree : 모든 vertex를 지나는 tree의 subgraph

 Property 3

   Li에 있는 각각의 vertex에 대하여 

   - s에서 v로 이루어진 Ts의 path는 i 개의 edge를 가진다.

   - Gs에서 s에서 v로 이루어진 모든 path는 최소 i개의 edge를 가진다.

---

동작 과정

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

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

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

---

Analysis

• vertex/edge label을 Setting/getting 하는데 O(1) time이 걸린다. (여기서 label은 상태 ex) visited, discovery, cross )
• 각 vertex는 2번 label이 지정된다.(UNEXPLORED / VISITED)
• 각 edge는 2번 label이 지정된다. (UNEXPLORED /  DISCOVERY or CROSS)
• 각 vertex는 sequence Li에 한 번 삽입된다.
• Method incidentEdges는 각 vertex에서 한 번 호출된다.
• n = 정점 수(vertex), m = 간선 수(edge)일 때, 그래프가 Adjacency List structure로 표현될 경우 O(n+m)
  => vertex와 연결된 모든 vertex를 살펴 보는 과정의 총합이 방향 그래프에서는 m, 무방향 그래프에서는 2m
• n = 정점 수(vertex)일 때, 그래프가 Adjacency Matrix로 표현될 경우 O(n^2)

---

Pseudocode

aa

 

Python Implementation

def BFS(g, s, discovered): # Graph g, starting aat Vertex s
	level = [s] # first level includes only s
    while len(level) > 0:
    	next_level = []
        for u in level:
        	for e in g.incident_edges(u):
             v= e.opposite(u)
             if v not in discovered:
             	discovered[v] = e
                next_level.append(v)
        level = next_level

 from collections import deque

# BFS 메서드 정의
def BFS(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8], # 1번 노드와 인접한 노드
    [1, 7], # 2번 노드와 인접한 노드
    [1, 4, 5], # 3번 노드와 인접한 노드
    [3, 5], # 4번 노드와 인접한 노드
    [3, 4], # 5번 노드와 인접한 노드
    [7], # 6번 노드와 인접한 노드
    [2, 6, 8], # 7번 노드와 인접한 노드
    [1, 7] # 8번 노드와 인접한 노드
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False]*9

# 정의된 BFS 함수 호출
BFS(graph, 1, visited)

---

C++ Implementation

#include <iostream>
#include <string>
#include <utility>
#include <Queue>
using namespace std;
#define X first // pair에서 first, second 줄여서 쓰기 위해 사용
#define Y second

int board[502][502] = { // 1이 blue, 0이 red
 {1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} };

bool vis[502][502]; // 해당 칸 방문 여부 저장
int n = 7, m = 10; // n = number of row, m = number of column
int dx[4] = { 1, 0, -1, 0 }; // 상하좌우 네 방향 의미(영리하게 처리)
int dy[4] = { 0, 1, 0, -1 }; // 하, 우, 좌, 상

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<pair<int, int> > Q;
	vis[0][0] = 1; // (0, 0)을 방문했다고 명시
	Q.push({ 0, 0 }); // 큐에 시작점인 (0, 0)을 삽입

	while (!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();
		cout << '(' << cur.X << ", " << cur.Y << ") -> ";
		for (int dir = 0; dir < 4; dir++) { // 상하좌우 칸을 살펴볼 것임
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
			if (nx < 0 || nx >= n || ny < 0 || ny > m) //범위 밖일 경우 넘어감
				continue; 
			if (vis[nx][ny] || board[nx][ny] != 1) // 이미 방문한 칸이거나 파란 칸이 아닐 경우
				continue;
			vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
			Q.push({ nx, ny });
		}
	}
}

---

참고 : 이것이 취업을 위한 코딩 테스트다 with 파이썬, 바킹독 알고리즘