3187 양치기 꿍

flood fill 을 응용하여 풀면 된다.

맵을 입력받으면서 v,k의 총 숫자를 세어 놓고 char[i][j] == '.'일 때 dfs를 돌려서 v,k의 숫자를 센다.

조건에 맞춰 v혹은 k의 총 숫자를 줄여나가면 된다.

#include <stdio.h>
using namespace std;
 
int r, c, cnt[2], cnt2[2], dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
char map[252][252];
 
void dfs(int x, int y) {
    if (map[x][y] == 'v') cnt2[0]++;
    else if (map[x][y] == 'k') cnt2[1]++;
    map[x][y] = '#';
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c || map[nx][ny] == '#') continue;
        dfs(nx, ny);
    }
}
 
int main() {
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; i++) {
        scanf(" %s", &map[i]);
        for (int j = 0; j < c; j++) {
            if (map[i][j] == 'v') cnt[0]++;
            else if (map[i][j] == 'k') cnt[1]++;
        }
    }
    for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) {
        cnt2[0] = cnt2[1] = 0;
        if (map[i][j] != '#') dfs(i, j);
        if (cnt2[1] > cnt2[0]) cnt[0] -= cnt2[0];
        else cnt[1] -= cnt2[1];
    }
    printf("%d %d\n", cnt[1], cnt[0]);
    return 0;
}