(C++) - 백준(BOJ) 6186번 : Best Grass

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

6186번: Best Grass

bfs또는 간단한 구현문제였습니다.

 

덩어리가 1번만 인접하거나 1개의 풀만 있는 경우만 주어지기 때문에 단순 brute force로도 해결할 수 있으나 bfs로 구현해봤습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

목장의 n행 m열을 입력받고, 모양을 이차원 char형 배열인 pasture에 입력합니다. 영역의 개수를 세는 변수 cnt를 선언합니다.

 

📔 풀이과정

 한 번도 방문하지 않은 구역은 cnt를 1 더한뒤 bfs를 수행해 영역에 겹침이 없도록 합니다. 그렇게 모든 n행 m열의 구역에 대해 조건에 따른 bfs를 수행한다면 풀 덩어리의 크기를 구할 수 있습니다.

 

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, m, ck[101][101], cnt;
int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0}; 
char pasture[101][101];

void bfs(int a, int b){
    ck[a][b] = 1;
    queue <pii> q;
    q.push({a,b});
    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(0 > nr || nr >= n || 0 > nc || nc >= m) continue;
            if(ck[nr][nc] || pasture[nr][nc] == '.') continue;
            ck[nr][nc] = 1;
            q.push({nr,nc});
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> pasture[i][j];
        }
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(ck[i][j] || pasture[i][j] == '.') continue;
            cnt++;
            bfs(i,j);
        }
    }
    cout << cnt << '\n';
}