6186 : Best Grass (C++)

6186번: Best Grass

---

BFS 또는 DFS를 이용하면 간단하게 풀 수 있는 문제이다.

문제 해석을 하자면 #을 세면 되는데 #은 가로 또는 세로로 붙어있을 수 있다.

요즘 영어문제 푸는게 재미있어졌는데 영어 독해 실력도 늘고 코딩실력도 늘고

재미져잉~~ 나도 얼른 코딩천재~~ 알고리즘 천재~~

#include<iostream>
#include<string>
#include<queue>

using namespace std;

char map[100][100];
bool visit[100][100];

int R, C, result;

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

queue<pair<int, int>> q;

// BFS
void bfs(int r, int c) {
    visit[r][c] = true;

    while(!q.empty()) {
        r = q.front().first;
        c = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(nr >= 0 && nr < R && nc >= 0 && nc < C) {
                if(map[nr][nc] == '#' && visit[nr][nc] == false) {
                    q.push({nr, nc});
                    visit[nr][nc] = true;
                }
            }
        }
    }
    
}

// DFS
void dfs(int r, int c) {
    visit[r][c] = true;

    for(int i = 0; i < 4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(nr >= 0 && nr < R && nc >= 0 && nc < C) {
            if(map[nr][nc] == '#' && visit[nr][nc] == false) {
                dfs(nr, nc);
            }
        }
    }
}

int main() {
    scanf("%d %d", &R, &C);

    for(int r = 0; r < R; r++) {
        string temp;
        cin >> temp;
        for(int c = 0; c < C; c++) {
            map[r][c] = temp[c];
        }
    }

    for(int r = 0; r < R; r++) {
        for(int c = 0; c < C; c++) {
            if(map[r][c] == '#' && visit[r][c] == false) {
                result++;
                /*
                BFS
                q.push({r, c});
                bfs(r, c);
                */

                // DFS
                dfs(r, c);
            }
        }
    }

    printf("%d\n", result);

    return 0;
}