BFS(Breadth First Search)

BFS(깊이 우선 탐색) 알고리즘

주로 맵 탐색을 하거나 최단 거리를 찾는데 사용된다. 백준에서는 2차원 배열로 이루어진 맵을 주고 그 안에서 문제를 해결하는 유형을 많이 볼 수 있다. 보통 이러한 문제들은 BFS나 DFS로 해결한다.

구현은 주로 queue 자료형을 이용하여 구현한다.

동작 원리

시작 노드를 방문하고 큐에 넣음
큐에서 노드를 꺼내 인접한 모든 미방문 노드를 큐에 추가
큐가 빌 때까지 반복

구현 방법

맵 탐색을 할 경우

c++

dy[] = [1, 0, -1, 0];
dx[] = [0, 1, 0, -1];

과 같이 위, 아래, 왼쪽, 오른쪽 4방면의 좌표를 나타내는 배열을 만들어주고,

c++

for(int i = 0 ; i < 4 ; i++) {
	int ny = y + dy[i];
	int nx = x + dx[i];
	
	if(!inBound(ny,nx)) continue;
	
	q.push({ny,nx});
}

이런 식으로 4 방향으로 이동한 좌표 ny, nx를 만든다.

만약 ny와 nx가 영역 밖이라면 continue를 사용하여 queue에 넣지 않는다.

또한 visited 배열을 사용하여 방문한 좌표에 다시 방문하지 않도록 한다.

제일 처음에는 visited 배열은 모두 -1로 초기화 시켜둔 상태에서

만약 방문하게 된다면 visited[y][x]에 현재 방문 순서를 넣으면 된다.

전체 BFS 함수 코드는 아래와 같다.

문제에 따라 조금의 변형이 필요할 수 있다.

c++

int map[n][m]; // input에서 받은 맵
int visited[n][m]; // -1로 모두 초기화

bool inBound(int y, int x) {
    return (y >= 0 
				    && y < n 
						&& x >= 0 
						&& x < m); // n: 행 개수, m: 열 개수
}

void bfs(int y_first, int x_first) {
	
	queue<pair<int,int>> q; // y좌표, x좌표
	visited[y_first][x_first] = 0;
	q.push({y_first, x_first}); //시작점 넣기
	
	while(!q.empty()) {
		// queue의 맨 앞에 있는 좌표를 가져오고
		int y = q.front().first; 
		int x = q.front().second;
		// 사용한 좌표는 삭제시키기
		q.pop();
		
		for(int i = 0 ; i < 4 ; i++) {
			// 다음 좌표 설정
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			// 범위 밖이라면 queue에 넣지 않기
			if(!inBound(ny,nx)) continue;
			// 이미 방문했다면 queue에 넣지 않기
			if(visited[ny][nx] != -1) continue;
			
			// 다음 좌표의 방문 순서는 이전 좌표 + 1
			visited[ny][nx] = visited[y][x] + 1;
			// 좌표 다시 queue에 넣기
			q.push({ny,nx});
		}
	}
}

visited 배열에는 queue가 FIFO(first in first out)이기 때문에 가능한 경로 중 가장 최단거리가 저장되게 된다.

예시) 백준 #2178 미로 탐색

c++

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int maze[100][100];
int visited[100][100] = {0,};
int cnt[100][100] = {0,};

int n,m;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};

queue<pair<int,int>> q;


void bfs(void)
{
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        visited[y][x] = 1;
        q.pop();

        if(x == m-1 && y == n-1 )
        {
            break;
        }

        for(int i = 0 ; i < 4 ; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx>=0 && nx<m && ny>=0 && ny<n && visited[ny][nx] == 0 && maze[ny][nx] == 1)
            {
                visited[ny][nx] = 1;
                cnt[ny][nx] = cnt[y][x] + 1;
                q.push({nx,ny});
            }
        }
    }
}

int main()
{
    cin>>n>>m;

    for(int i = 0 ; i < n ; i++)
    {
        string str;
        cin>>str;
        for(int j = 0 ; j < m ; j++)
        {
            maze[i][j] = str[j] - '0';
        }
    }

    q.push({0,0});
    bfs();

    cout << cnt[n-1][m-1] + 1;
  

}

먼저 맵을 string으로 입력 받고, 맵으로 만들어준다. 그리고 bfs 큐에 (1 , 1)을 넣어주고, (n, m)을 찾을 때까지 bfs를 돌려준다. 도착할 수 없는 경우는 없으므로 찾으면 탐색을 종료한다.