[알고리즘 정리] BFS

Taegang Yun·2024년 4월 16일

알고리즘 정리

목록 보기

3/7

BFS는 그래프라는 자료구조에서 노드를 방문하기 위한 알고리즘이다.

우리의 목표는 (0,0)과 상하좌우로 이어진 모든 파란색 칸을 확인하는 것이다.

우선 BFS 알고리즘에서는 좌표를 담을 큐가 필요하다.
BFS 알고리즘이 시작되면 우선 (0,0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다.
이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 된다.

지금 상황에서 큐의 front는 (0,0)이고 pop을 한다. 그리고 (0,0)의 상하좌우 칸을 보는데, 이 중에서 우리는 파란색 칸이면서 아직 방문하지 않은 칸을 찾는다.

.....

시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
큐가 빌 때까지 2번을 반복
시간복잡도는 칸이 N개일 때 O(N)

#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(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    queue<pair<int, int>> Q;
    vis[0][0] = 1;
    Q.push({0, 0});
    while(!Q.empty()){
    	pair<int, int> cur = Q.front(); Q.pop();
        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;
            if(vis[nx][ny] || board[nx][ny] != 1) continue;
            vis[nx][ny] = 1;
            Q.push({nx, ny});
        }
    }
}

응용 1 - 거리 측정

BFS를 이용해 시작점에서 연결된 다른 모든 점으로의 최단 경로를 찾을 수 있다.

거리를 저장할 dist 배열을 두고 상하좌우의 칸을 볼 때 값을 잘 넣어주면 된다.
이 배열을 미리 -1로 초기화 해두면 굳이 vis배열을 따로 두지 않아도 방문 여부를 확인할 수 있다.

미로탐색

// Online C++ compiler to run C++ program online
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#define fastio cin.tie(0), ios_base::sync_with_stdio(0)

using namespace std;


int n, m;
int board[102][102];
int dist[102][102];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1 ,0, -1};
int y, x;


int main() {
   fastio;
   cin >> n >> m;
   string str;
   for(int i = 0 ; i < n; i++){
       cin >> str;
       for(int j = 0; j < m; j++){
           board[i][j] = str[j] - '0';
       }
   }
   fill(&dist[0][0], &dist[0][0] + 102 * 102, -1);
   
   dist[0][0] = 0;
   queue<pair<int, int>> q;
   q.push({0, 0});
   while(!q.empty()){
       tie(y, x) = q.front(); q.pop();
       for(int i = 0 ; i < 4; i++){
           int ny = y + dy[i];
           int nx = x + dx[i];
           if(ny < 0 || nx < 0 || ny >= n || nx >=m) continue;
           if(board[ny][nx] == 0 || dist[ny][nx] > -1) continue;
           dist[ny][nx] = dist[y][x] + 1;
           q.push({ny, nx});
       }
   }
   
   cout << dist[n-1][m-1] + 1<< '\n';
}