📌 알고리즘 - BFS 개념
너비 우선 탐색이란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다.
인접 리스트로 표현된 그래프:
인접 행렬로 표현된 그래프:
그래프 내에 적은 숫자의 간선을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[502][502];
bool vis[502][502];
int n = 7, m = 10;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(){
queue<pair<int,int>> Q;
vis[0][0] = 1; // 시작 정점 방문 처리
Q.push({0,0}); // 큐에 push
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];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 보드를 벗어나면 continue
if (vis[nx][ny]) continue; // 이미 방문한 정점이면 continue
vis[nx][ny] = 1; // 방문 처리
Q.push({nx,ny}); // 큐에 push
}
}
}