[알고리즘] 개념 - BFS (너비 우선 탐색)

공혁준·2022년 6월 8일
0

알고리즘 개념

목록 보기
4/5
post-thumbnail

📌 알고리즘 - BFS 개념

너비 우선 탐색이란?

너비 우선 탐색이란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다.

  • 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점은 나중에 방문한다.
  • 깊게 탐색하는 DFS와 달리 BFS는 넓게 탐색한다.
  • 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 알고리즘을 사용한다.

너비 우선 탐색의 특징

  • BFS는 재귀적으로 동작하지 않는다.
  • 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
  • 방문한 노드들을 차례대로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.

너비 우선 탐색의 시간 복잡도

인접 리스트로 표현된 그래프: O(N+E)O(N+E)
인접 행렬로 표현된 그래프: O(N2)O(N^2)
그래프 내에 적은 숫자의 간선을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

너비 우선 탐색의 구현

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int board[502][502];
bool vis[502][502];
int n = 7, m = 10;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
    queue<pair<int,int>> Q;
    vis[0][0] = 1; // 시작 정점 방문 처리
    Q.push({0,0}); // 큐에 push
    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];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 보드를 벗어나면 continue
            if (vis[nx][ny]) continue; // 이미 방문한 정점이면 continue
            vis[nx][ny] = 1; // 방문 처리
            Q.push({nx,ny}); // 큐에 push
        }
    }      
}
profile
몰입을 즐기는 개발자입니다.

0개의 댓글