[Algorithm][BFS] BFS 개념 및 구현

I. BFS(Breadth First Search)란?

BFS기본 구조

너비 우선 탐색 BFS는 인접한 점을 우선 탐색하는 알고리즘이다.
공기가 퍼지는 원리라고 생각하면 쉽다. 인접한 부분을 모두 탐색하고 다음 단계로 확산한다.

기본적으로 탐색의 개념을 가진 BFS는 모든 점을 다! 확인해야 한다.
-> 공간 복잡도 O(N)
-> 시간 복잡도 O(N+B)  (N : node, B : branch) 

주로 배열(map)이 주어지고 미로찾기, 길 찾기 등 Search문제로 출제된다.

---

II. 기본 원리

하나의 방향을 정하면 쭉 끝까지 타고 들어가는 DFS와 다르게,
방문 순서를 정해야 하는 BFS이므로 순서를 저장할 수 있는 Queue 자료구조를 이용한다.

Ex)
1. 0에 방문하여 연결된 1과 2를 Queue에 저장
2. Queue.pop() 으로 1로 방문하여 3과 4를 Queue에 저장 (이때 Queue : (2,3,4))
3. Queue.pop() 으로 2로 방문하여 5와 6을 Queue에 저장 (이때 Queue : (3,4,5,6))
4. 이하 반복.

!!주의 - 방문했던 Node는 재방문 금지.

---

III. 구현 코드

1. 가중치가 없이 단순히 전체를 방문하는 코드. 
    10x10의 배열 map[0][0] 출발, map[9][9] 도착

<hide/>
#include <queue> // c++의 Queue STL
#include <iostream>
#include <cstring> // memset위해서
using namespace std;

/*
배열의 인덱스, 현재까지의 시간 구조체
Queue에 정보를 다 넣어야하기 때문에 구조체 정의함.
*/
struct stu{
    int y;
    int x;
    int time;
};

queue<stu> Q;
int map[10+2][10+2]; // 지도
int visit[10+2][10+2]; //방문을 표시하는 지도

int BFS(){
    // 상하좌우 탐색 위한 dy,dx
    int dy[4] = {0,0,-1,1};
    int dx[4] = {1,-1,0,0};
    
    // Q에 초기정보를 stu구조로 push함 (map[0][0]과 time =0)
    Q.push(stu{0,0,0}); 
    visit[0][0] = 1; // Q에 넣을 때 방문처리
    
    //Q가 텅 빌때까지 반복(모든노드 탐색)
    while(!Q.empty()){
        stu curstu = Q.front(); //현재정보
        Q.pop(); //큐에서 제거
        
        //4가지 방향을 모두 확인해본다.
        for(int d=0;d<4;d++){
            // 다음정보를 계산해줌
            int nextx = curstu.x+dx[d];
            int nexty = curstu.y+dy[d];
            int nexttime = curstu.time +1;
            
            //다음이 목적지면 그냥 return해서 끝내버림
            if(nexty == 9 and nextx == 9) return nexttime;
            
            if(nexty == -1 or nextx == -1 or
               nexty == 10 or nextx == 10) continue; // 배열 벗어나면 무시
            
            if(visit[nexty][nextx]) continue; // 방문했다면 무시
            
            Q.push(stu{nexty,nextx,nexttime}); // 다음 정보 Q에 Push
            visit[nexty][nextx] = 1; // 방문표시 (꼭 넣을 때 해주어야 함 - 언제 pop될지 모르니)
        }
    }
    return -1; // 목적지 못찾으면 -1 반환 - 현재는 의미없음.
}
    
int main(){
    memset(map,0,sizeof(map));
    memset(visit,0,sizeof(visit));
    int ans = BFS();
    
    cout<<ans; // 18
    
    return 0;
}
    

2. 가중치가 있는 경우 (ex. 가장 적은 비용으로 가는 법)
    map의 각 위치에 통과시 지불해야하는 비용이 입력되어있다고 할 때, 가장 적은비용의 길로 가면 얼마?

<hide/>
#include <queue> // c++의 Queue STL
#include <iostream>
#include <cstring> // memset위해서
using namespace std;

/*
배열의 인덱스, 현재까지의 시간 구조체
Queue에 정보를 다 넣어야하기 때문에 구조체 정의함.
*/
struct stu {
	int y;
	int x;
	int cost; // *
};

queue<stu> Q;
int map[10 + 2][10 + 2]; // 지도

// **방문표시는 의미가 없어지며 그 위치로 오기위한 누적 Cost를 넣어준다.
int visitcost[10 + 2][10 + 2];

int BFS() {
	// 상하좌우 탐색 위한 dy,dx
	int dy[4] = { 0,0,-1,1 };
	int dx[4] = { 1,-1,0,0 };

	// Q에 초기정보를 stu구조로 push함 (map[0][0]과 time =0)
	Q.push(stu{ 0,0,0 });
	visitcost[0][0] = 0; // 초기위치 cost 0;

	//Q가 텅 빌때까지 반복(모든노드 탐색)
	while (!Q.empty()) {
		stu curstu = Q.front(); //현재정보
		Q.pop(); //큐에서 제거

		//4가지 방향을 모두 확인해본다.
		for (int d = 0; d < 4; d++) {
			// 다음정보를 계산해줌
			int nextx = curstu.x + dx[d];
			int nexty = curstu.y + dy[d];

			if (nexty == -1 or nextx == -1 or
				nexty == 10 or nextx == 10) continue; // 배열 벗어나면 무시

			 // map에 접근해야하므로 if문 이후에 선언
			 // 현 위치까지 누적 Cost(visit) + 다음 위치의 Cost(map)
			int nextcost = curstu.cost + map[nexty][nextx];

			// *이번 경우는 Q에 Push 할 때 Cost확인 조건이 들어간다.
			// *내가 현재 위치에서 넘어갔을 때의 Cost가 이득일때만 Q.push해줌.
			if (nextcost < visitcost[nexty][nextx]) {
				Q.push(stu{ nexty,nextx,nextcost }); // 다음 정보 Q에 Push
				visitcost[nexty][nextx] = nextcost; // * Cost 업데이트해줌. 
			}
		}
	}
	return visitcost[9][9]; // 내 도착지점의 visit배열에 Cost가 기록되어있다.
}

int main() {
	memset(map, 0, sizeof(map));
	fill(&visitcost[0][0], &visitcost[10][10], INT32_MAX); // 최대값으로 초기화

	// 각 위치에 cost입력 0~9
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			map[i][j] = j;
		}
	}

	int ans = BFS();

	cout << ans; // 45

	return 0;
}

 

3. 기타 응용

BFS에서 Queue를 사용하고 visit배열을 사용하는 것은 거의 동일하다.
문제마다 달라지는 점은
1. Q.push()를 하기위해 추가해주어야 하는 조건식
2. Visit 배열에 무엇을 담을 것인가? 이다.

만약, 구현 도중 메모리 Limit가 발생한다면, visit배열을 해결하고,
                       시간 Limit이 발생한다면, continue 혹은 return 가지치기를 신경써보자.