record logo record

Algorithm

너비 우선 탐색(BFS, Breadth First Search)

update: 16 September 2020

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

algorithm-animated_bfs

너비 우선 탐색(Breath First Search)의 알고리즘 예시

BFS 구현

아래와 같은 형태의 그래프가 주어질때 BFS를 구현 해보겠습니다.

1─2─5
|/ \│
3   4
|\
6─7

C++ BFS 구현 예시1

인접 리스트 가 입력 값으로 주어진 상황에서 C++ STL Library로 구현한 BFS 코드입니다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 1~7번 노드의 방문 처리 하기 위한 배열 
int c[7];
vector<int> a[8];
void bfs(int start){
	queue<int> q;
	q.push(start);
	c[start] = true;
	//search
	while(!q.empty()){
		int x = q.front();
		q.pop();
		printf("%d ", x);
		for(int i = 0; i < a[x].size(); i++){
			int y = a[x][i];
			// 방문한 상태가 아니라면 큐에 넣어준다.
			if(!c[y]){
				q.push(y);
				c[y] = true; 
			}
		}
	}
}
int main(void){
	int input[8][2] = {
		{1,2},{1,3},{2,3},{2,5},{2,4},{3,6},{4,5},{6,7}
		};
	//data input
	for (int i = 0; i < 8; i++) {	
		a[input[i][0]].push_back(input[i][1]);
		a[input[i][1]].push_back(input[i][0]);
	}
	
	bfs(1);
	
	return 0;
}

C++ BFS 구현 예시2

인접 행렬 이 입력 값으로 주어진 상황에서 C++로 구현한 BFS 코드입니다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{
 {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}
}; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
  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});
    }
  }
}

Java BFS 구현 예시1

인접 리스트 가 입력 값으로 주어진 상황에서 Java Collection으로 구현한 BFS 코드입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class Main {
	static int[][] input = { 
		{1,2},{1,3},{2,3},{2,5},{2,4},{3,6},{4,5},{6,7}
		};
	static LinkedList<Integer>[] board = new LinkedList[8];
	static boolean[] visit = new boolean[8];

	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visit[start] = true;

		while(!q.isEmpty()) {
			int cur = q.poll();
			System.out.print(cur + " ");
			for (int i = 0; i < board[cur].size(); i++) {
				int next = board[cur].get(i);
				if(!visit[next]) {
					q.add(next);
					visit[next] = true;
				}
			}
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//init
		for (int i = 1; i <= 7; i++) {
			board[i] = new LinkedList<>();
		}
		//input
		for (int i = 0; i < input.length; i++) {
			board[input[i][0]].add(input[i][1]);
			board[input[i][1]].add(input[i][0]);
		}
		bfs(1);
		br.close();
	}
}

BFS 문제 유형(+응용 유형)

주의할점

BFS 연습문제

Reference