BFS

컴퓨터로 문제를 풀 때, 보통 그 문제는 탐색을 기반으로 합니다.

문제가 정의하고 있는 '공간'을 탐색합니다. 

상태를 논리적으로 정의할 수 없다면, 모든 공간을 커버한다는 보장이 없기 때문에

해가 맞는 것인지 판별할 수 없습니다.

그 다음 공간은 이전의 상태를 통해 발생하기 때문에, 트리처럼 공간이 뻗어 나갑니다.

그 공간을 방문하는 방법 중에 'BFS'와 'DFS'가 있습니다.

지금은 BFS(Breadth First Search)를 설명하려고 합니다.

 

영어 뜻 그대로 넓이 우선 탐색이다. 트리의 가지를 따라서 무작정 들어가지 않고, 

depth를 하나씩 늘려갑니다. 아래는 BFS와 DFS를 비교하는 그림입니다.

문제에 따라 어떤 방문 방법을 선택해야 정답을 빠르게 찾을 수 있을 것인지

판단하고 적용해야 합니다. 전형적인 문제로는 미로찾기 문제가 있습니다. 또는,

영역을 나누는 문제도 있다. BFS가 어떻게 움직이는지 아래 그림을 통해서 확실히

알아야 합니다. 문제의 상태 공간을 방문한다는 개념도 중요하지만, 이 움직임이 

문제에서 적용시켰을 때 맞는 움직임이라면 적용해보는 것입니다.

이를 위해 사용하는 자료구조로는 'queue'와 방문한 곳을 재방문하지 않기 위한 'visited 배열' 정도가 있습니다.

(주의!) 만약 visited 배열을 깜빡 잊고 사용하지 않을 경우 메모리 초과 또는 시간 초과가 발생할 수 있습니다. 

문제를 특정 알고리즘으로만 풀 수 있다고 단정 짓는 것을 싫어하는 편입니다. 그래도 문제라는 것은 역시

어떠한 것이든 카테고리가 있는 것이기에, '이 문제가 BFS 문제구나!' 라고 어떤 것을 보고 감을 잡는지 공유해보겠습니다.

'이동할 수 있는 가장 빠른 시간', '바이러스처럼 무엇인가 퍼져나가는 시뮬레이션', '컴포넌트의 갯수 구하기', 

'도착지점으로 가는데 필요한 최소 변환 횟수' 등.. 이 정도를 해내야 하는 문제라면 가장 먼저 BFS를 의심해볼 수

있습니다. 그 다음은 직접 생각을 해봐서 이게 BFS로 될 문제인지 시간안에, 메모리 안에 해낼 수 있는지 확신이

있을 경우 그 때 구현을 시작하면 됩니다.

일부러 BFS를 사용하도록 유도하는 문제도 있고, 제한 시간이나 메모리를 빡빡하게 줘서 다른 알고리즘을

함께 사용해야 할 수도 있습니다. 아니면 BFS로는 쉽게 해결할 수 없는 구조의 문제라던지 문제는 엄청나게

많아요. ㅠㅠ

보통 코딩은 아래와 같은 스타일로 하면 됩니다. 예를 든 것이기 때문에 문제에 따라 다르게 작성해야 합니다.

struct tt{
    int cnt;
    int y, x;
};
 
queue<tt> q;
q.push({0,0,0});
 
while(!q.empty()){
    tt f = q.front();
    q.pop();
    
    if( // 답을 구하였을 경우 ){
        cout << f.cnt << endl;
        return 0;
    }
    for( ... ){
        // 필요한 경우 range 검사
        // 답을 구하기 위해 반복적으로 해야하는 로직 작성    
    }
 
}

[출처 : 나무위키]

문제를 풀어보자.

토마토(https://www.acmicpc.net/problem/7576) 이다.

우선 익은 토마토 위치를 저장해 놓는다.

익은 토마토 주위를 확인해가며, 안익은 토마토가 있으면 익히고, 이것을 큐가 빌때까지 계속하면

익을 수 있는 토마토는 모두 익을 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <math.h>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <regex>
#include <sstream>
#include <utility>
#include <list>
 
int m, n;
int mp[1001][1001];
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };
bool chk[1001][1001];
 
struct s {
    int y, x, cnt;
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> m >> n;
 
    queue<s> q;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == 1) {
                q.push({ i,j,0 });
            }
        }
    // 1 : 익 / 0 : 안익 / -1 : 없음
    int mx = 0;
    while (!q.empty()) {
        s temp = q.front();
        q.pop();
 
        mx = max(mx, temp.cnt);
 
        for (int dir = 0; dir < 4; dir++) {
            int ny = temp.y + dy[dir], nx = temp.x + dx[dir];
            int nc = temp.cnt + 1;
            if (ny < 0 || ny >= n || nx < 0 || nx >= m || mp[ny][nx] != 0) continue;
            mp[ny][nx] = 1;
            q.push({ ny,nx,nc });
        }
    }
 
    for(int i =0; i < n;i++)
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == 0) {
                cout << -1;
                return 0;
            }
        }
 
 
    cout << mx;
 
    return 0;
 
}
 

이 문제를 만약 DFS로 풀게 된다면 문제점은 무엇일까?

DFS로 불가능한 것은 아니다. 단지 처리해야 할 것이 BFS로 풀 때보다 매우 많고, 실수할 가능성도 많다.

지금 방문한 토마토가 언제 익을 것인지를 처리해주어야 하는데 이것이 골치 아플 것이다.

하지만 BFS로는 현실에서와 비슷하게 시뮬레이션을 할 수 있기 때문에, 그대로 코드를 작성하면 된다. 

[다른 문제]

1. 탈출(https://www.acmicpc.net/problem/3055)

2. 효율적인 해킹(https://www.acmicpc.net/problem/1325)

3. 유기농 배추(https://www.acmicpc.net/problem/1012)

4. 현수막(https://www.acmicpc.net/problem/14716)

5. 폴짝폴짝(https://www.acmicpc.net/problem/1326)

6. 미로탐색(https://www.acmicpc.net/problem/2178)

7. 안전영역(https://www.acmicpc.net/problem/2468)

8. 게임(https://www.acmicpc.net/problem/1103)

9. bad grass(https://www.acmicpc.net/problem/6080)

10. 나이트의 이동(https://www.acmicpc.net/problem/7562)

11. 상범 빌딩(https://www.acmicpc.net/problem/6593)

12. 스타트링크(https://www.acmicpc.net/problem/5014)

13. 촌수 계산(https://www.acmicpc.net/problem/2644)

14. 다리 만들기(https://www.acmicpc.net/problem/2146)

15. 소수 경로(https://www.acmicpc.net/problem/1963)

16. BFS와 DFS(https://www.acmicpc.net/problem/1260)

17. 빙산(https://www.acmicpc.net/problem/2573)