[C++#4-2] BFS

BFS에 대해 작성한 이 글에서는 글을 읽는 사람들이 그래프, 큐에 대한 기본적인 지식이 있다고 생각하고 작성했다.

1. BFS(Breadth-First Search) 

사전에서 정의하는 BFS의 정의는 아래와 같다.

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 

다음과 같은 그래프가 있다고 생각해보자.

그래프의 모든 정점을 순회하고자 할 때, DFS는 하나의 길씩 탐색했다면

BFS는 하나의 정점에서 갈 수 있는 경로들을 동시에 탐색하는 것이다.

아래의 영상과 같이 탐색한다고 생각하면 된다.

1-1. 그래프

글의 시작에서도 언급했다싶이 BFS는 큐를 사용한다.

큐에서 다음에 탐색할 정점 or 위치를 저장(push)하고, 다음에 탐색할 정점이 없다면 큐에서 해당 정점을 삭제(pop)한다.

위의 그래프를 BFS로 탐색하는 과정은 아래와 같다.

먼저 시작점인 정점 1을 큐에 push 한다.

정점 1에서 갈 수 있는 정점 2와

정점 3을 push한 후,

정점 1을 pop해준다. 현재 위치는 정점 2로 변경된다.

정점 2에서 갈 수 있는 정점 4와

정점 6을 push한 후,

정점 2를 pop한다. 현재 위치는 정점 3으로 바뀐다.

정점 3에서 탐색할 수 있는 정점 7을 push하고,

정점 3을 pop한다. 현재 위치는 정점 4로 바뀐다.

정점 4에서 갈 수 있는 정점 5와

정점 8을 push하고,

정점 4를 pop해준다. 현재 위치는 정점 6이 된다.

정점 6에서는 탐색이 더이상 불가능하므로 정점 6을 pop해주고,

마찬가지로 정점 7,

정점 5도 pop해준다.

정점 8에서 탐색할 수 있는 정점 9를 push해준다.

정점 8에서 더이상 탐색이 불가능하므로 정점 8을 pop해주고,

정점 9도 pop해준다.

큐가 비어있으므로 탐색을 종료한다.

1-2. 코드

BFS도 DFS와 마찬가지로 2차원 배열에서의 BFS를 구현할 것이다.

DFS때와 마찬가지로 S는 출발점, F는 도착점을 나타낸다.

전체적인 코드는 아래와 같다.

#include <iostream>
#include <queue>
 
using namespace std;
 
int map[5][5] = { { 0, 0, 0, 0, 0 },
                    { 1, 1, 0, 1, 0 },
                    { 0, 0, 0, 0, 0 },
                    { 0, 1, 0, 1, 1 },
                    { 0, 0, 0, 0, 0 } };
 
bool checkmap[5][5] = { { false, false, false, false, false },
                    { false, false, false, false, false },
                    { false, false, false, false, false },
                    { false, false, false, false, false },
                    { false, false, false, false, false } };
 
int distmap[5][5] = { { 0, 0, 0, 0, 0 },
                    { 0, 0, 0, 0, 0 },
                    { 0, 0, 0, 0, 0 },
                    { 0, 0, 0, 0, 0 },
                    { 0, 0, 0, 0, 0 } };
 
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0,-1 };
 
int minn = 25;
 
struct p {
    int y;
    int x;
};
 
void bfs(int y, int x);
p makeP(int y, int x);
 
int main() {
    bfs(0, 0);
    minn = distmap[4][4];
 
    cout << minn;
}
 
void bfs(int y, int x) {    
    
    queue<p> Queue;
    Queue.push(makeP(y, x));
    checkmap[y][x] = true;
 
    while (!Queue.empty()) {
 
        p curPosition = Queue.front();
        Queue.pop();
        int curY = curPosition.y;
        int curX = curPosition.x;
 
        for (int i = 0; i < 4; i++) {
            int ny = curY + dy[i];
            int nx = curX + dx[i];
 
            if (ny < 0 || ny > 4 || nx < 0 || nx > 4 || map[ny][nx] == 1) continue;
            if (checkmap[ny][nx] == true) continue;
 
            Queue.push(makeP(ny, nx));
            checkmap[ny][nx] = true;
            distmap[ny][nx] = distmap[curY][curX] + 1;
        }
    }
}
 
p makeP(int y, int x) {
    p P;
    P.y = y;
    P.x = x;
    return P;
}

코드가 DFS에 비해서 훨씬 복잡한데 하나하나씩 설명해보겠다.

1-2-1. queue?

DFS에서는 스택을 사용한다 하고 재귀함수를 사용했는데, 

BFS에서는 다행히도 큐를 사용한다 하고 그대로 큐를 사용했다.

큐를 사용하기 위해 C++ STL에서 재공하는 queue를 include해주면 큐를 쉽게 사용할 수 있다.

1-2-2. distmap? checkmap?

DFS와는 다르게 기존에 맵에 두개의 맵이 더 추가되었다.

물론 맵을 줄이자면 두개의 맵으로도 BFS를 할수는 있지만, 맵의 원형을 유지하기 위해 3개의 맵을 사용했다.

1-2-2-1. checkmap?

checkmap은 DFS의 checkmap과 마찬가지로 방문한 정점을 체크하기 위한 용도이다.

DFS때와 다르게 bool 형태의 2차원 배열로 사용했는데, 사실 checkmap의 용도는 '방문 했다' 또는 '방문 하지 않았다' 두가지의 상태를 담는 것을 목적으로 함으로 0, 1대신 false, true를 사용했다.

크게 차이는 없지만 메모리를 생각한다면 bool로 선언하는 것이 더 좋을것이다.

1-2-2-2. distmap?

distmap은 이동 거리를 담기 위한 map이다.

위에 말한 것처럼 map에다가 이동거리를 저장할 수도 있다.

하지만 BFS를 한번만 할 경우에는 상관 없지만, map의 원형을 유지한 상태로 BFS를 여러번 수행해야 하는 경우에 map의 원형이 변형되면 문제가 생긴다.

이런 상황을 방지하기 위해 distmap이라는 거리를 저장하는 map을 만들고, 초기 거리를 0으로 설정한 후,

다음 위치에 이전 거리 + 1을 해 거리가 1씩 증가하도록 설정했다.

1-2-3. struct p? makeP?

struct p는 2차원 배열의 좌표를 저장하기 위한 구조체 변수이다.

선언 부분을 보면 struct p는 int y, int x 두가지의 변수를 갖고 있다.

DFS에서는 재귀함수를 호출하면서 매개변수를 통해 현재의 위치를 계속 넘겨주었지만, 

BFS에서는 무한반복문에서 큐를 사용하므로 큐에 현재의 위치가 포함되어 있어야 한다.

y좌표와 x좌표를 queue에 한번에 저장하기 위해 구조체를 사용했다.

makeP는 y, x를 p에 저장하는 함수이다. 코드를 깔끔하게 적기 위해 만들었다.

1-2-4. while(!Queue.empty)

무한 반복은 큐가 비어있을 때까지 계속하고, 탐색을 완료한 정점은 무한반복문의 처음 부분에서 pop해준다.

++

dy, dx나 minn의 경우는 DFS에서 설명했으므로 생략하겠다.

1-3. 결과

이 코드를 실행하면 최종적으로 모든 위치로의 최단경로를 포함한 하나의 맵이 나올 것이다.

결과 값은 8이 나올 것이고,

cout으로 출력하면

DFS와 마찬가지로 8이 출력된다.

 

++ 개인적인 생각

DFS와 BFS 두개 다 완벽하게 다룰수 있는 것이 베스트이지만,

만약 시간적으로 코딩테스트를 준비하는데에 여유가 부족하다면 BFS를 먼저 하는 것을 추천한다.

DFS에 비해 코드가 복잡하지만, 원리에 대해 이해하면 생각보다 간단하고

코딩테스트에서 자주나오는 2차원 맵을 탐색할 때, BFS로 하는 것이 시간복잡도가 훨씬 낮다.