백준 3184번 - 양

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

백준에는 BFS로 분류되어 있지만

단순하게 마당별로 완전 탐색으로도 풀 수 있어서 DFS로 문제를 분류했다.

(사실 BFS가 큐에 담는 다는 것 외에는 접근 방식은 동일하다)

풀이 방식은 다음과 같다.

1) 해당 칸이 '#' 인지, 방문을 했는지 체크한다.

2) 만약 '#'이거나 방문을 했다면 1번으로 돌아가 다음 칸을 체크한다.

3) 만약 '#'이 아니며 방문을 하지 않았다면 해당 칸의 인접한 4개의 칸을 탐색한다.

4) 탐색이 끝났을 때, 한 마당에서 양과 늑대의 수를 비교해 더 큰 값을 최종적인 양과 늑대의 수에 더해준다.

#include <iostream>
#include <vector>
using namespace std;
 
vector<vector<char>> map;
vector<vector<int>> visited;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int R,C;
 
int total_sheep_cnt=0; //최종 양의 수
int total_wolf_cnt=0; //최종 늑대 수
int sheep_cnt=0; //마당에 있는 양의 수
int wolf_cnt=0; //마당에 있는 늑대 수
 
void dfs(int y,int x){
    
    if(map[y][x]=='o')  sheep_cnt++;
    else if(map[y][x]=='v') wolf_cnt++;
    
    for(int dir=0;dir<4;dir++){
        int ny=y+dy[dir];
        int nx=x+dx[dir];
        
        if(ny<0 || ny>=R || nx<0 || nx>=C)
            continue;
        
        if(map[ny][nx]=='#' || visited[ny][nx])
            continue;
        
        visited[ny][nx]++;
        dfs(ny,nx);
    }
}
int main(){
    
    cin>>R>>C;
    map=vector<vector<char>> (R,vector<char>(C,0));
    visited=vector<vector<int>> (R,vector<int>(C,0));
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            cin>>map[i][j];
        }
    }
    
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(map[i][j]!='#' && !visited[i][j]){
                visited[i][j]++;
                sheep_cnt=0;
                wolf_cnt=0;
                dfs(i,j);
                
                if(sheep_cnt>wolf_cnt)  total_sheep_cnt+=sheep_cnt;
                else    total_wolf_cnt+=wolf_cnt;
            }
        }
    }
    
    cout<<total_sheep_cnt<<" "<<total_wolf_cnt<<endl;
    return 0;
}