백준 5958 Space Exploration (USACO January 2011 Bronze 3번)

문제 링크: https://www.acmicpc.net/problem/5958

5958번: Space Exploration

DFS

component의 갯수를 세면 됨.

#include <bits/stdc++.h>
using namespace std;
 
int n, v[1001][1001], dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1};
char a[1001][1001];
 
void dfs(int y, int x) {
    v[y][x] = 1;
    for(int d = 0; d < 4; d++) {
        int yy = y + dy[d], xx = x + dx[d];
        if(yy >= 0 && xx >= 0 && yy < n && xx < n) {
            if(!v[yy][xx] && a[yy][xx] == '*')
                dfs(yy, xx);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
        cin >> a[i][j];
 
    int ans = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
        if(!v[i][j] && a[i][j] == '*') {
            dfs(i, j);
            ans++;
        }
    }
 
    cout << ans << '\n';
    return 0;
}