[백준] 14716번 : 현수막

문제

https://www.acmicpc.net/problem/14716

14716번: 현수막

 

주안점

기본적인 BFS에서 사용하는 상,하,좌,우 에다가 대각선이 포함된 이동을 한다.

 

 

구조

BFS를 통하여 Visited로 확인하며 몇번 BFS를 돌았는지 확인

 

 

코드

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

int row,col,ret,y,x;
int a[254][254], visited[254][254];
queue<pair<int,int>> q;

int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};

int main() {
    cin>>row>>col;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            cin>>a[i][j];
        }
    }
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(a[i][j]==1 && visited[i][j]==0){
                ret++;
                visited[i][j] = 1;
                q.push({i,j});
                while(q.size()){
                    tie(y,x) = q.front(); q.pop();
                    for(int k=0; k<8; k++){
                        int ny = y+dy[k];
                        int nx = x+dx[k];
                        if(ny>=row || nx>=col || nx<0 || ny<0) continue;
                        if(visited[ny][nx]==1 || a[ny][nx]==0) continue;
                        visited[ny][nx] = 1;
                        q.push({ny,nx});
                    }
                }
            }
        }
    }
    cout<<ret<<"\n";
}