백준 11123 - 양 한마리... 양 두마리...(C++)

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

11123번: 양 한마리... 양 두마리...

간단한 4방향 그래프 탐색 문제입니다.

map이 주어졌을 때, 양 무리가 얼마나 있는지 구하는 문제입니다.

양이 있는 곳을 찾은 뒤, 해당 좌표에서 4방향 탐색을 이어가서 얼마나 양이 이어져 있는지 확인합니다.

탐색이 있을 때마다 양 무리를 하나씩 증가시켜주면 됩니다.

 

 

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <cstdio>
#define P pair<int, int>
#define PP pair<P, int>
#define F first
#define S second

using namespace std;

int N, M, T;
char map[101][101];
int check[101][101];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

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

void solve(){
    for(int t = 1; t <= T; t++){
        int cnt = 0;
        memset(check,0,sizeof(check));
        cin >> N >> M;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                cin >> map[i][j];
            }
        }
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(map[i][j] == '#' && check[i][j] == 0){
                    bfs(i,j);
                    cnt++;
                }
            }
        }
        cout << cnt << "\n";
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    solve();
    return 0;
}

 

 

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