[백준/C++] 14716번 현수막

백준

---

🤔문제 이해

상, 하, 좌, 우, 대각선 4방향으로 인접한 1을 한 글자로 취급하여 글자가 몇개 있는지 구하는 문제이다.

---

🔥풀이🔥

정말 간단한 BFS 문제인데 방향이 4개 더 추가된 버전이다.

방향을 표현해주는 dx와 dy를 다음과 같이 선언해서 오른쪽, 왼쪽, 위쪽, 아래쪽, 오른쪽 아래, 왼쪽 아래, 오른쪽 위, 왼쪽 위를 나타내주었다.

 

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

---

#include <iostream>
#include <queue>
using namespace std;

int m, n;
int map[251][251];
bool visited[251][251];
queue<pair<int,int>> q;

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

bool isValid(int y, int x){
    return x >=0 && y >=0 && x < n && y < m && !visited[y][x];
}

void BFS(){
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for(int i=0; i < 8; i++){
            int mv_y = y + dy[i];
            int mv_x = x + dx[i];
            if( isValid(mv_y, mv_x) && map[mv_y][mv_x] == 1) {
                q.push({mv_y, mv_x});
                visited[mv_y][mv_x]= true;
            }
        }
    }
}

int main (){
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> m >> n;
    for(int i=0; i < m; i++){
        for(int j=0;j < n; j++){
            cin>> map[i][j];
        }
    }
    int cnt =0;
    for(int i=0; i < m; i++){
        for(int j=0;j < n; j++){
            if(map[i][j] == 1 && !visited[i][j] ) {
                visited[i][j] = true;
                q.push({i, j});
                BFS();
                cnt++;
            }
        }
    }
    cout << cnt;
}