BFS

정의

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문

성질

• BFS를 돌 때 큐에 원소(좌표)가 쌓이는 순서는 언제나 시작점으로부터의 거리 순이다.

과정

1. 시작점 방문 표시하고 큐에 넣기(push)
2. 큐에서 원소를 꺼내고(front + pop) 해당 칸과 상하좌우로 인접한 칸들의 방문 표시 여부 확인
   2-1. 처음 방문 : 방문 표시하고 큐에 넣기(push)
   2-2. 이미 방문 : 아무것도 하지 않기
3. 큐가 empty 될 때까지 2번을 반복

방문 표시를 남기기 때문에 모든 칸이 큐에 1번씩만 들어가므로 칸이 N개일 때 시간 복잡도는 O(N)이다.

✏️ STL pair

• utility 헤더
• 두 자료형을 묶어서 가지고 다닐 수 있다. ??
• BFS 시 큐에 좌표를 넣을 때 사용한다.

BFS 구현 기본 코드

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

#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용

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}}; // 1이 파란 칸, 0이 빨간 칸에 대응

bool vis[502][502]; // 해당 칸의 방문 여부를 저장

int n = 7, m = 10; // n = 행의 수, m = 열의 수

// 특정 칸의 상하좌우로 이동
int dx[4] = {1,0,-1,0}; // 행 방향 이동
int dy[4] = {0,1,0,-1}; // 열 방향 이동

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  queue<pair<int,int> > Q;
  vis[0][0] = 1; // 시작점인 (0, 0) 방문 표시
  Q.push({0,0}); // 큐에 삽입
  
  while(!Q.empty()){
    pair<int,int> cur = Q.front(); // cur = current 즉, 현재 방문한 칸의 좌표 저장
    Q.pop();
    
    cout << '(' << cur.X << ", " << cur.Y << ") -> "; // 방문 순서를 알리기 위한 출력
    
    // 방문한 칸의 상하좌우 방문하기
    // X = 행, Y = 열
    for(int dir = 0; dir < 4; dir++){ 
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir]; // dir에서 정한 방향에 따른 인접한 칸의 좌표가 들어감
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // board 배열의 범위 밖에 존재하는 칸일 경우 pass
      
      if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우 pass
      
      vis[nx][ny] = 1; // (nx, ny) 방문 표시
      
      Q.push({nx,ny}); // 큐에 삽입
    }
  }
}

✅ 배열의 크기가 [502][502]인 이유

n과 m의 최대값이 500이므로 안정성을 위해 padding 주어 사용한다.

✅ dx와 dy를 조합하여 상하좌우로 이동

• x : 행 인덱스 (위 → 아래로 갈수록 증가)
• y : 열 인덱스 (왼 → 오로 갈수록 증가)

int dx[4] = {1,0,-1,0};  // 행 방향 이동 (아래, 제자리, 위, 제자리)
int dy[4] = {0,1,0,-1};  // 열 방향 이동 (제자리, 오른쪽, 제자리, 왼쪽)

• x 고정 : (x, y-1) , (x, y+1)
• y 고정 : (x-1, y) , (x+1, y)

• dx[0] dy[0] → (1,0) 만큼 이동 : 아래
• dx[1] dy[1] → (0,1) 만큼 이동 : 오른쪽
• dx[2] dy[2] → (-1,0) 만큼 이동 : 위
• dx[3] dy[3] → (0,-1) 만큼 이동 : 왼쪽

✅ if(nx < 0 || nx >= n || ny < 0 || ny >= m) 처리

배열의 인덱스는 0부터 시작하므로 board[n][m] 의 유효한 인덱스 범위는 아래와 같다.

• 행(nx)의 유효 범위: 0 ≤ nx < n
• 열(ny)의 유효 범위: 0 ≤ ny < m

즉, nx 또는 ny가 n 또는 m이 되면 배열의 범위를 초과하므로 nx >= n , ny >= m 로 검사해야 한다.

출력

⚠️ 주의사항

1. 시작점에 방문했다는 표시 남기지 않으면 시작점을 두 번 방문하게 될 수 있다.
2. 큐에서 pop() 실행 시 방문 표시를 하면 같은 칸이 여러 번 들어가게 되어 시간 초과나 메모리 초과가 될 수 있다.
3. 해당 칸의 이웃한 원소가 범위 안에 존재하는지 체크해야 한다.