[BOJ - 6186] Best Grass(C++)

  문제

  접근방법

문제를 해석하지 않아서 잘 모르겠는데

4963번: 섬의 개수

이 문제와 비슷하다고 판단 (#이 있는 지역의 개수)

dx, dy로 상하좌우로 이동할 수 있게 선언한 후 DFS로 연결된 #을 모두 탐색하면 되겠다고 생각

 

  코드

#include <iostream>

using namespace std;

int R, C;

const int Max_size = 101;
char map[Max_size][Max_size];
bool visited[Max_size][Max_size];

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


bool inArea(int x, int y) {
    return x >= 0 && y >= 0 && x < R && y < C;
}

void dfs(int x, int y) {
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (inArea(tx, ty) && !visited[tx][ty] && map[tx][ty] == '#') dfs(tx, ty);
    }
}

int cnt_shop() {
    int shop = 0;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (!visited[i][j] && map[i][j] == '#') {
                dfs(i, j);
                shop++;
            }
        }
    }

    return shop;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cin >> map[i][j];
    }

    cout << cnt_shop();

    return 0;
}

 

  링크

6186번: Best Grass