BFS(Breadth-First-Search) 넓이 우선 탐색

BFS는 넓이 우선 탐색으로 이름에서 알 수 있게 넓게 탐색하는 알고리즘이다.

쉽게 말하면 가장 가까운 부분부터 탐색하며 점차 넓혀가는 알고리즘이다.

 

BFS는 가장 가까운 부분부터 탐색하기에 최단거리를 탐색할 때 유리하다.

만약에 특정 맵에서 key를 찾아야할 때 BFS를 이용한다면 현재 위치에서 가장 가까운 부분부터 탐색하다 Key를 찾는 순간 탐색을 멈추면 이것이 최단거리이기 때문이다.

해당 거리에서 Key를 찾는 최단거리가 몇인지 구한다면 BFS를 사용하면 쉽게 구할 수 있다.

 

int BFS(pair<int, int> pos, vector<vector<char>>& board)
{
	int pathCount = 0;
    
    //현재 위치와 이동 횟수를 저장하는 큐
	queue<pair<pair<int, int>, int>> q;
    
    //상하좌우 탐색을 위한 방향 저장
	pair<int, int> direction[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
    
    //방문한 노드를 재방문할 필요가 없으니 재방문 노드를 저장
    vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
    
    //초기 위치 큐에 저장
    q.push({pos, pathCount});
    
    //큐(다음에 이동할 위치)가 빌때까지 반복
    while(!q.empty())
    {
    	//큐에서 정보 추출
    	pair<pair<int, int>, int> current = q.front();
        //정보에서 위치 추출
        pair<int, int> currentPos = current.first;
        
        //정보를 추출했으니 큐 제거
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
        	//이동할 위치 계산
        	int ny = currentPos.first + direction[i].first;
            int nx = currentPos.second + direction[i].second;
            
            //이동할 위치가 범위를 벗어나거나 이미 방문했는지 체크
            if(ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size() || visited[ny][nx])
            	continue;
            
            //이동할 위치가 벽인지 체크
            if(board[ny][nx] == 'B')
            	continue;
            //이동할 위치가 키인지 체크
            if(board[ny][nx] == 'K')
            {
            	//키면 찾은것이니 현재 이동 거리를 반환
            	return current.second;
            }
            // 큐에 넣기 전에 방문 처리
			visited[ny][nx] = true;
			
            //이동할 수 있는 위치이면 다음 위치와 이동 거리를 1추가해 큐에 추가
            q.push({ {ny, nx}, current.second + 1});
            
        }
    }
    
    return -1;
}

큐를 이용해 다음으로 움직일 위치를 저장하며 진행한다면 가까운 거리부터 큐에 차곡차곡 쌓이게 된다. 이후 큐에서 정보를 한개씩 꺼내다가 조건이 만족하면 큐에 정보가 얼마나 남아있던지 반환해서 함수를 종료시키면 된다.

여기서 중요한 점은 방문한 노드를 확인하는 것이다.

 

BFS는 같은 방법으로 노드를 검사하기에 방문한 노드는 이미 이전에 같은 값을 검사했을 것이고 BFS는 최소 값을 구하기에 이전에 검사한 값이 더 최솟값일 것이다. 때문에 이미 방문한 노드는 이후 검사할 필요가 없다.

 

BFS는 현재 위치에 상하좌우를 검사 후 다음 큐에 넣기 때문에 다음 위치에서 이전 위치를 검사할 수도 있다. 이렇게 되면 무한루프에 빠지거나 성능이 느려질 것이다.(검사했던 곳을 계속 큐에 넣어 재검사 하기 때문에) 

 

때문에 BFS는 모든 노드를 확인하지 않아도 최단거리를 구할 수 있으며 모든 노드를 확인하는 DFS보다 높은 성능을 보인다.

 

DFS에 대한 자세한 설명은 아래 블로그에 정리하였다.

https://jinho082008.tistory.com/58

DFS( Depth-First Search) 깊이 우선 탐색