[템플릿] - BFS

BFS 템플릿

1.좌표상 4방향 이동

#define X first
#define Y second
int board[502][502] ={...};
bool vis[502][502];
int N,M;//입력값
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(void){
	queue<pair<int,int>> Q;
    vis[0][0]=1;
    Q.push{(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];
        //제한조건 1: 범위 초과 
        if(nx<0 || nx >=n || ny<0 || ny>=m) continue;
        //제한조건 2: 방문했던 위치 아닌 경우 
        if(vis[nx][ny] || board[nx][ny] != 1) continue;
        vis[nx][ny] = 1;
        Q.push({nx,ny});
    }
}