백준(boj)3184 - 양

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

👀문제이해 및 풀이방법

기본적인 bfs문제이다. 처음에 양이나 늑대의 위치를 저장해두고 그곳만 탐색해볼까 했지만 들이는 메모리 낭비에비해 줄어드는 시간복잡도가 작다고 생각해서 모든 곳을 시작위치의 후보로 두었다

visit 배열을 통해 늑대나 양인 곳에서만 출발하고 또 이미 갔던곳은 안가도록 하였다

bfs를 돌때마다 양과 늑대의 수를 비교해서 더 작은 것을 전체 양,늑대 수에서 빼주면 금방 답이 나온다

📝코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
class yang{
private:
    vector<vector<char>> map;
    int R,C;
    vector<vector<bool>> visit;
    int S=0,W=0;
public:
    yang(){
        std::cin >> R >>C;
        map.resize(R,vector<char>(C));
        visit.resize(R,vector<bool>(C,false));
        set_val();
    }
    void set_val(){
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                std::cin >> map[i][j];
                if(map[i][j]=='v')
                    W++;
                else if(map[i][j]=='o')
                    S++;
            }
        }
    }
    void bfs(int x,int y){
        queue<pair<int,int>> q;
        q.push({x,y});
        visit[x][y]=true;
        pair<int,int> cur;
        int nx,ny;
        int o_cnt=0,v_cnt=0;
        while(!q.empty()){
            cur = q.front();
            q.pop();
            if(map[cur.first][cur.second]=='v')
                v_cnt++;
            else if(map[cur.first][cur.second]=='o')
                o_cnt++;

            for(int i=0;i<4;i++){
                nx=cur.first+dx[i],ny=cur.second+dy[i];
                if(nx>=0 && nx<R && ny>=0 && ny<C){
                    if(!visit[nx][ny] && map[nx][ny]!='#'){
                        visit[nx][ny]=true;
                        q.push({nx,ny});
                    }
                }
            }
        }
        if(o_cnt>v_cnt)
            W-=v_cnt;
        else
            S-=o_cnt;
    }
    void find_sol(){
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(!visit[i][j] && (map[i][j]=='v' || map[i][j]=='o'))
                    bfs(i,j);
            }
        }
        std::cout << S <<' '<< W <<'\n';
    }

};
int main(){
    yang yg;
    yg.find_sol();

    return 0;
}