BFS

BFS 알고리즘

1. 시작하는 칸을 큐에넣고 방문했다는 표시를 남김

2. 큐에서 원소를 꺼내고, 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
   3-1. 해당 칸을 처음 방문한다면 => 방문했다는 표시를 남기고, 해당 칸을 큐에 삽입
   3-2. 이전에 이미 방문한 칸이라면 => 아무것도 하지 않음

3. 큐가 빌 때까지 2번을 반복

시간 복잡도

• 모든 칸이 큐에 1번씩만 들어가므로, 시간복잡도는 칸이 N개일 때 O(N)
• 만약 R x C 의 배열일 경우 O(RC)

STL pair

• 좌표 표현

• 헤더 < utility >

• 값 할당방법 : make_pair 로 값을 넣어줄수도 있고, 그냥 중괄호를 써서 값을 할당도 가능

• 알아서 앞쪽의 first 값을 먼저 비교후, 뒤쪽의 값을 비교

#include <bits/stdc++.h>
using namespace std;

int main(void){
  pair<int, int> t1 = make_pair(10,13);
  pair<int, int> t2 = {4,6};
  
  cout << t1.first << ' ' << t2.second << '\n';
}

BFS 구현

#include <bits/stdc++.h>
using namespace std;

// 1이면 데이터가 있는 칸, 0이면 없는 칸
int board[502][502] = {
	{1,1,1,0,1,0,0,0,0,0},
	{1,0,0,0,1,0,0,0,0,0},
	{1,1,1,0,1,0,0,0,0,0},
	{1,1,0,0,1,0,0,0,0,0},
	{0,1,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,0,0,0}
};

bool visited[502][502];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int n = 7, m = 10;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int, int>> Q;

    // BFS 탐색을 시작하는 칸을 (0,0)으로 잡았다.
    // 좌표 (0,0) 을 방문 처리하고, 큐에 push
    visited[0][0] = 1;
    Q.push({ 0,0 });

    // 큐가 빌 때까지 그 칸의 상하좌우의 칸을 추가하는것을 반복
    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();
        Q.pop();

        cout << '(' << cur.first << ", " << cur.second << ") -> ";

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i]; // 상하좌우 칸에 대한 좌표 데이터 저장
            int ny = cur.second + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;

            if (visited[nx][ny] || board[nx][ny] != 1)
                continue;

            visited[nx][ny] = 1; // 방문 처리하고 상하좌우 칸을 큐에 push
            Q.push({ nx,ny });
        }

참고 - BFS 구현시 자주하는 실수

1. 시작점에 방문했다는 표시를 남기지 않는경우

• 이렇게 되면, 시작점을 2번 방문할 수 있다!

2. 큐에 넣을때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남기는 경우

• 같은 칸이 큐에 여러번 들어가게 되어서 런타임 에러 발생

3. 상하좌우 좌표 (nx, ny) 가 정상적인 범위를 벗어났는지에 대한 체크를 잘못한 경우

지난번 스터디 내용 보충 😓

• 설명 모호하게 설명드린 점 사과드리며.. 😥
• BFS 는 왜 큐를 사용해서 구현하는가?
  • 1. 순서보장 : BFS 는 노드를 방문한 순서대로 그 노드와 인접한 노드들을 탐색한다! -> 큐는 FIFO 이므로, 노드를 방문한 순서대로 처리 가능하다.
  • 2. 메모리 효율 : BFS는 모든 노드를 한 번씩만 방문하므로, 큐에는 한 번에 모든 노드가 저장되지 않는다.
  • 3. 중복 방지 : BFS는 노드를 한 번 방문하면 그 노드를 다시 방문하지 않는다. 큐를 사용하면 이미 방문한 노드를 효과적으로 관리할 수 있다!