백준 14716 - 현수막(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14716

14716번: 현수막

8방향 탐색을 하는 간단한 BFS 문제였습니다.

0과 1로 이루어진 map에서 1로만 이루어진 영역을 찾는 문제였습니다. 다른 문제와는 다르게 대각선까지 포함한 8방향 탐색을 해야됨을 유의했다면 쉽게 풀 수 있던 문제입니다.

 

먼저 map을 전부 확인해본후, 1이 있는 곳을 확인합니다. 이때, 이전에 방문했던 곳은 아니여야 합니다.

조건을 만족했다면 해당 점부터 8방향 탐색을 시작해 글자가 어디까지 이어져있는지를 확인합니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#define P pair<int,int>

using namespace std;


int N, M;
int map[251][251];
int dx[8] = {1,0,-1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,-1,-1,1};
int check[251][251];

void bfs(int X, int Y){
    queue<P> q;
    q.push({X,Y});
    check[X][Y] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 8; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(map[xx][yy] == 1 && check[xx][yy] == 0){
                    check[xx][yy] = 1;
                    q.push({xx,yy});
                }
            }
        }
    }
}

void solve(){
    int cnt = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == 1 && check[i][j] == 0){
                bfs(i,j);
                cnt++;
            }
        }
    }
    cout << cnt;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요