BFS
J-Shine
바킹독님의 실전알고리즘배우기 9강듣고 요약
BFS 과정
BFS는 너비우선탐색 알고리즘으로, 큐를 이용하며 시작점에서 점점 퍼져나가는 문제 해결에 잘 쓰인다.
깊이가 1인 노드를 모두 탐색 하면서 깊이가 2인 노드를 차례로 큐에 넣고, 깊이가 1인 노드 방문이 모두 끝나면 큐에서 하나씩 꺼내서 방문하며 깊이가 3인 노드를 큐에 넣고.. 큐가 빌 때까지 반복
깊이는 시간, 거리, 단계 등으로 치환하여 생각할 수 있다.
1차원일 때 시간복잡도가 O(N)이고, 2차원일 때는 행이 R개, 열이 C개라고 하면 시간복잡도가 O(RC)이다.(컴퓨터는 1초에 1억번의 연산을 할 수 있음을 참고)
BFS 코드 예시
위 그림의 파란색 칸을 BFS로 모두 탐색하는 코드
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
// 문제에서 파란칸은 1, 빨간칸은 0으로 board에 설정 (블로그에 올릴 때 자꾸 오류가 떠서 지웠음)
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}); // 큐에 시작점인 (0, 0)을 삽입.
while(!Q.empty()){
pair<int,int> cur = Q.front(); Q.pop();
cout << '(' << cur.X << ", " << cur.Y << ") -> ";
for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 방문 안 함
if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우도 방문 안 함
vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
Q.push({nx,ny});
}
}
}
자세한건 주석에 설명
BFS를 돌릴 때는 보통 n과 x가 행이고, m과 y가 열이다.
그리고 위의 #define X first, #define Y second를 할 때 끝에 세미콜론이 붙지 않는다!!
세미콜론을 붙이면 define한 X, Y 사용시 에러가 나므로 주의
BFS 구현시 실수하기 쉬운 것들
